Reference no: EM13168130
In class we discussed Karatsuba's divide-and-conquer algorithm for integer multiplication, which multiplies n-bit numbers by recursively multiplying n bit numbers. We take two numbers X and Y and split them each into their most significant half and least significant half: X = 2^n/2A + B and Y = 2^n/2C + D. Now, we can write the product
XY =(2^n - 2^n/2)AC+2^n/2(A+B)(C+D)+(1-2^n/2)BD.
Using this relation, write pseudocode for a recursive function Karatsuba(X,Y,n) to multiply two n-bit numbers X and Y . You may assume that you have access to a routine shift(U,m) that will shift the number U by m bits to the left (you may use negative values of m to shift to the right) as well as access to routines add(U,V) and subtract(U,V) that respectively compute U + V and U - V and run in linear time. You can assume that the usual -, /, +, and * operators can be used on small numbers (like n) as well as on X and Y for your base-cases when n <=4.
If you like, you can assume you have a split(X,A,B) operator that splits X into its left and right halves A and B, but see if you can implement this using the shift operator.
|
United broke artists (uba) is a broker
: United Broke Artists (UBA) is a broker for not-so-famous artists. UBA maintains a small database to track painters, paintings, and galleries. A painting is created by a particular artist and then exhibited in a particular gallery
|
|
You are to create a program
: You are to create a program that will input a group of floating point values, storing them as double values in an array. This array will then be sent to three functions.
|
|
You are the admissions office at abc medical university
: You are the Admissions Office at ABC Medical University. You have a large number of applicants for a very few number of available openings at your school. As a result, you need to set some high admission standards. To be accepted, a student ..
|
|
Numbers until the user wants and in the end display
: Write a C program to enter the numbers until the user wants and in the end display the product of numbers entered by the user. The program should terminate once the user enters the character 'n' and continue computing product if user enters 'y'
|
|
Karatsuba''s divide-and-conquer algorithm
: In class we discussed Karatsuba's divide-and-conquer algorithm for integer multiplication, which multiplies n-bit numbers by recursively multiplying n bit numbers. We take two numbers X and Y and split them each into their most significant half a..
|
|
Creates an array of six divsales objects
: Write a program that creates an array of six DivSales objects. The program should ask the user to enter the sales for four quarters for each division. After the data are entered, the program should display a table showing the division sales for ..
|
|
Create a class in java to enable its object to be persiste
: How do you create a class in Java to enable its object to be persistent? What are Java data streams and how are they used to facilitate storage and retrieval of persistent objects?
|
|
A sorting algorithm is described as stable
: A sorting algorithm is described as stable if equal elements are in the same relative order in the sorted sequence as in the original sequence.
|
|
Create a flowchart that programs a robot to recognize
: Create a flowchart that programs a robot to recognize how many playing cards you have and to put them in order from smallest to largest
|