Author Topic: booth's algorithm  (Read 6524 times)

Offline tejaswi2195

  • Jr. Member
  • *
  • Posts: 9
booth's algorithm
« on: February 19, 2014, 02:53:51 PM »
sorry for troubling you guys again.


i have implemented booth's algorithm for 8 bit multiplication .
the last two digits in result are correct but some problem is there with other digits.

if anyone knows booth's algorithm for multiplication can you tell me where am i going wrong.

thanks in advance...

Offline encryptor256

  • Full Member
  • **
  • Posts: 250
  • Country: lv
  • Win64 .
    • On Youtube: encryptor256
Re: booth's algorithm
« Reply #1 on: February 19, 2014, 04:47:08 PM »
Are those your school assignments?

I think, not help you, is the right solution for this and for you.
Encryptor256's Investigation \ Research Department.

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: booth's algorithm
« Reply #2 on: February 20, 2014, 01:21:36 PM »
Well, I'm not going to "do your homework for you", but that isn't what's being asked. I'll "help" if I can. Unfortunately, I don't know Booth's Algorithm. I read up on it on WIKI, and I still don't "get" it. My brain's not in "math mode" today (maybe any day). Even with your (nicely commented!) implementation, it's pretty mysterious to me.

But "fools rush in" so I've been flailing about in it, "fixing" things that look like they "might" be wrong. To start with, you define "num1" (etc.) as "resb 3". Then you move rbx into it. Since you do this "in order" - overwriting "future variables" then filling them in with correct values - I don't think this is actually doing any harm, but I changed 'em to "resq 1". Didn't help a bit, but I left it that way. If they're really a byte, "resb 1" ought to be enough. "resb 3" is a strange size for a variable (correct for your input buffer, however!), but doesn't seem to be a problem.

Going the other way, per Bryant's suggestion, you use "movzx rax, byte [num1]", etc. I wondered, since Booth's algorithm apparently expects to work with signed numbers (if I got that part) whether we should be using "movsx" to sign extend a byte into a qword. Doesn't seem to help. In particular, where you negate "num1" and put it in "num1c" I'm thinking that this should be a whole 64-bit negative number. Doesn't seem to help.

Since the problem seems to manifest as the low two hex digits being correct, but some "bonus" digits above that, I tried meddling with the mask you use to "truncate the carry". Tried keeping 16 bits, and 15 (I think 17 is what you want). Doesn't seem to help. I can make it more wrong, but I can't seem to get it right. Not too much of a surprise, since I don't really know what I'm trying to do. :)

So I guess I'm following Encryptor256's suggestion and not helping you. I may get back to it - re-read Booth until I get it if trial and error continues to fail. Just didn't want you to think you'd been totally abandoned here. Good luck!

Best,
Frank