1
$\begingroup$

I have two numbers x and y. The upper bits of x are stored at location m, while the lower bits of x are stored at location n. The upper bits of y are stored at location i, while the lower bits of y are stored at location j.

I have the division operator "/" and the multiplication operator "*", but only for numbers stored at a single memory location. For example, if q was small enough to be stored at memory location a, and p was small enough to be stored at memory location b, then I can compute q/p and store this in a single memory location.

The question is: how do I compute x/y and x*y in the fastest way? I was thinking along the lines of using / and * in places where I am only multiplying parts of the number at one memory location, because this would be faster than strictly using repeated addition or repeated subtraction.

For specifics, I am using the language 7800basic, where numbers can only be 1 byte large. And I am looking to be able to multiple and divide larger numbers in the fastest way.

$\endgroup$
  • 1
    $\begingroup$ For multiplication take a look on Karatsuba multiplication. For dividing I think you can adopt Long division method from school. $\endgroup$ – knok16 Aug 27 '15 at 10:15
  • $\begingroup$ For a multiplication of numbers twice the word length, forget any asymptotically advantageous methods, including Toom-Cook (which includes Karatsuba). $\endgroup$ – greybeard Aug 27 '15 at 16:06
  • $\begingroup$ Why's that, Greybeard? Surely Karatsuba is better than repeated addition. ... $\endgroup$ – joeyfernau Aug 27 '15 at 16:37
  • $\begingroup$ What methods for division and multiplication of such numbers have you used up to now? How many of each can you get completed in, say, 5 seconds, and how many would be enough? Is this an exercise, of are you pushing a "real" 6502? Can you incorporate code not generated by 7800basic? Is my impression correct that the biggest product supported is 255 (15*17)? $\endgroup$ – greybeard Aug 27 '15 at 19:24
  • $\begingroup$ I have only implemented repeated addition and repeated subtraction successfully. My testing method is not user friendly in the sense that I have to restart my Atari emulator every time I want to run my code. And the output is just sprites (images) on the screen which are numbers. So I haven't done such a test yet. I've just noticed that my create_line implementation (which uses these 2 byte numbers) is a little sluggish, which will cause problems when I do operations on top of this. 255 is the largest such number. I don't understand what pushing a 6502 is or incorporating non 7800basic code $\endgroup$ – joeyfernau Aug 27 '15 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.