64 bit addition/subtraction with Spin

Andy Gombos · 2008-01-15 20:49

I've been reading this forum for a while, and there are lots of smart people here; the community around the Propeller chip seems very active.

I have written a 64 bit -> 32 bit square root routine in PASM. It works fine, but after I used PASM I realized that Spin would provide a much cleaner control structure for the rest of the program, as well as remove the 496 long limit I was probably going to hit soon.

However, I can't think of a way to do 64 bit addition (and subtraction) with Spin. I don't particularly want to waste an entire cog for running square roots. I was looking into restarting the Spin interpreter at the end of my square root routine, but I don't think that would let me emulate a PASM function call (the old Spin interpreter state would be destroyed).

I know that Spin is going to be significantly slower, but that doesn't matter much for my application. I've attached the PASM routine in case someone has any alternate suggestions.

Thanks!

Mike Green · 2008-01-15 20:57

There's no access to the 33rd bit (carry) from Spin. If you can be satisfied with 63 bit arithmetic, you could do something like:

lowA := lowA + lowB   ' values must be no more than 31 bits
highA := highA + highB + (lowA >> 31)   ' carry from 31st bit
lowA &= $3FFFFFFF   ' remove carry in 32nd bit

Subtraction would be similar.

Tracy Allen · 2008-01-15 21:19

Alternatively, use the fact that lowA will end up less than lowB if there is a carry:

lowA := lowA + lowB   ' 32 bit unsigned values
highA := highA + highB - (lowA => lowB)

The Boolean value is true=0 if there is not a carry, and false=-1 with carry. The low long addition is always treated as unsigned. The overall value can be either signed or unsigned, with the sign in bit 63. Note that greater than or equal has to be written as =>.

Similar logic for subtract/borrow.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

CJ · 2008-01-15 21:30

wouldn't you be able to determine the carry bit by comparing the final value to one of the operands?

for addition if the result is less than either of the operands then you had a 1 in the carry(correct me if I am wrong, please)

for subtraction, if the result is greater than either of the operands then you had a 1 in the carry bit

just my thoughts

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Parallax Forums - If you're ready to learn, we're ready to help.

Phil Pilgrim (PhiPi) · 2008-01-15 21:33

Tracy,

Because the comparison is signed, lowA =< lowB (which is what I think you meant) could be true if there was no carry (e.g. $7FFF_FFFF + $7FFF_FFFF).

-Phil

deSilva · 2008-01-15 21:44

Andy Gombos said...
I know that Spin is going to be significantly slower, but that doesn't matter much for my application.

Timing must ALWAYS be considered; non-quantitative statements are useless...
Q1: How long does your SQRT take now?
Q2: What would you accept with SPIN?

Note there is always a response time and throughput aspect!

I should start a COG each time I needed a square root. Loading takes 100µs. Of course you need a COG, but that COG is versatile and re-usable..

Andy Gombos · 2008-01-15 22:10

deSilva said...

Q1: How long does your SQRT take now?

If I counted right, ~3500 cycles, so ~44us at 80Mhz

deSilva said...

Q2: What would you accept with SPIN?

It could take about .25 sec or so before it should start to become a problem (it's hard to say exactly because I'm guesstimating how long the physical system can pause while the calculation is being performed). At any rate, using your rough 80:1 Spin:PASM ratio, it would only be a few milliseconds - definitely fast enough.

deSilva · 2008-01-15 22:20

So it's no problem to just load, run, and forget an unattached COG.... = 150 µs

This algorithm could be one of the cases where SPIN will be even slower

So just for this benchmark I would be very interested in your SPIN implementation...

Tracy Allen · 2008-01-15 22:35

Phil, right, drat! I was thinking in Stampese and forgot that the comparisons are always signed in Spin. Not having unsigned compares does complicate that approach. Can't use
IF lowA<lowB THEN carry=1
either.

I think it can be salvaged by offsetting both sides by 2^31=2,147,483,648, so that the compare of the original values effectively becomes unsigned.
highA := highA + highB - (lowA + 2_147_483_648 => lowB + 2_147_483_648)
I'm not 100% confident in that though. Can't test it now and thinking fuzzy before afternoon stimulant!

I think I did mean, =>, not =<. Considering A => B as unsigned, it should generate a carry -(-1) when the condition is false, namely when A < B.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

Dave Hein · 2010-10-25 15:12

You could use SpinLMM ( http://obex.parallax.com/objects/635/ ) to run Spin and PASM in the same cog. However, if I were you I would just dedicate a cog to run the square root routine.

lonesock · 2010-10-25 16:52

OK, just hacked this up, so I do not trust the low bit of the result too much (it passed for a bunch of random trials using a 16-bit input). Also, the high long must fit in 31-bits (i.e. not be considered negative by Spin).

EDIT: I think I fixed the final bit.

PUB sqrt64( hi, lo ) : root | tmp, dbit
  ' reverse the lo long
  lo ><= 32
  ' start the comparison cycle
  repeat dbit from 30 to 0
    ' what is the delta if I add in this bit?
    tmp := ((root << 2) + 1) << dbit
    root <<= 1
    ' does this number fit?
    if( hi => tmp )
      ' yep!
      hi -= tmp
      root++
    ' move the next bit from lo into hi
    hi += hi + (lo & 1)
    lo >>= 1
  ' final bit
  hi += hi + lo
  root <<= 1
  if( hi - root - root - 1 => 0 )
    root++

Jonathan

Cluso99 · 2010-10-25 17:55

Since you seem to have some experience, I would use the Spin-LMM method suggested by Dave. This way you will get a much faster result and you can also add your other routines as LMM.

lonesock · 2010-10-25 20:59

I think I fixed the final bit (in the code above), and it takes ~187300 counts, so 2.34ms at 80MHz, about 54 x slower than your PASM code. It's definitely faster to start up a free cog and use your PASM code as needed, or go the LMM route. [8^)

Jonathan

max72 · 2010-10-26 05:40

Either use the SpinLMM, use a COG to do the job, or use the embedded pasm object.

If you use it to calculate a distance given the difference along two axis you can also use a cordic routine. It gives you back atan2 and dist with little effort.
This one can be implemented in spin, SpinLMM, in Pasm in a new Cog or in Pasm using the embedded object.

It depends on your needs...

So many options, so much power in your hands...

Massimo

rokicki · 2010-10-26 10:34

This is untested, but it's simple enough so I'm just going to post it.

clo = alo + blo ;
chi = ahi + bhi + (((alo >> 31) + (blo >> 31) + 1 - (clo >> 31)) >> 1) ;

I'm sure some of the experts here will be able to simplify it further.

64 bit addition/subtraction with Spin

Comments