50 bit maths

g3cwi · 2012-06-12 08:47

I need to do some maths (in Spin) that will need more than 32 bits. If I need say 50 bits, is the best way to break the calculation into 31 bits (to allow an overflow flag bit) and 19 bits?

Cheers

Richard

Leon · 2012-06-12 09:55

64-bit arithmetic would be more sensible!

g3cwi · 2012-06-12 10:01

The device I want to use needs 50 bits so why would I bother with 64?

Cheers

Richard

Phil Pilgrim (PhiPi) · 2012-06-12 10:18

It all depends upon which operations you need to perform. Addition and subtraction only? Multiplication? 25 x 25 = 50 or 50 x 50 = 100? Division? 50 / 50 = 50, or 100 / 50 = 50? Transcendental functions? Unsigned only, or mixed signed and unsigned? You need to specify to get a good answer to your query.

-Phil

g3cwi · 2012-06-12 10:25

Hi Phil

Unsigned integer add and subtract are all that I need

Regards

Richard

Duane Degn · 2012-06-12 10:32

The Propeller Wiki has some 64 bit math discussion.

Leon · 2012-06-12 11:05

g3cwi wrote: »

The device I want to use needs 50 bits so why would I bother with 64?

Cheers

Richard

You should be able to find some code that can be adapted. I doubt if you will find any 50-bit code.

g3cwi · 2012-06-12 11:15

Thanks for your help Leon. The question did not relate solely to 50 bit maths but rather to to maths >32 bits and <64 bits. The OP also was not asking for code but rather had a question that you have perhaps not read?

Cheers

Richard

ericball · 2012-06-12 11:28

>32 bit addition & subtraction is relatively easy to do in PASM. For 50 bit you would use two 32 bit longs for 64 bit and simply ignore the 14 highest bits (unless you need to handle 50 bit overflow). In SPIN it's a little harder because you don't have direct access to the carry bit and longs are implicitly signed. But I suspect there's a way to determine by looking at the signs of the least significant parts whether the carry would have been set and handle it appropriately. (i.e. to split the 50 bit value into 18 bit most significant and 32 bit least significant variables)

g3cwi · 2012-06-12 11:42

Thanks ericball. I will really have to get to grips with some PASM before too long.

Regards

Richard

ericball · 2012-06-12 12:13

Here's how addition would work: (Note: There may be more optimal ways to do this in SPIN.)

zlsb = xlsb + ylsb
if ( xlsb ^ ylsb > 0 )
  if ( xlsb > 0 )
    zmsb = xmsb + ymsb
  else
    zmsb = xmsb + ymsb + 1
else
  if ( zlsb < 0 )
    zmsb = xmsb + ymsb
  else
    zmsb = xmsb + ymsb + 1

The logic goes like this:
if the most significant bit of both least significant longs are zero, then there can be no carry. If both are one then there will always be a carry. If one is one and the other is zero, then if the most significant bit of the result of adding the least significant longs is zero then there was a carry, but if it is a one then there is no carry.

Subtraction is left as an exercise for the implementer.

ericball · 2012-06-12 12:37

Look Ma, no IFs:

zlsb = xlsb + ylsb
zmsb = xmsb + ymsb + ((xlsb | ylsb) & !zlsb | xlsb & ylsb ) >> 31

g3cwi · 2012-06-12 12:39

Cool! Thanks - now I just need to figure out how it works

Regards

Richard

ericball · 2012-06-12 13:35

The subtraction equation is a little more complex:

zlsb = xlsb - ylsb
zmsb = xmsb - ymsb - ( !xlsb & ylsb | ( !xlsb | ylsb ) & zlsb ) >> 31

Tracy Allen · 2012-06-12 23:44

That is cool Eric. Believe me, I had to get out the operator precedence chart and puzzle over it.

There sure are a lot of ways to skin the ca., oh! sorry Browser.

g3cwi · 2012-06-13 00:22

Hi Tracy

My task for tonight is to try to figure out how these work. Operator precedence will clearly be rather important!

Thanks ericball.

Regards

Richard

ericball · 2012-06-13 05:22

g3cwi wrote: »

Operator precedence will clearly be rather important!

Note: SPIN precedence is different (and more correct IMHO) from C precedence.

ericball · 2012-06-13 05:53

Another way of working it out is starting with the full adder equations:

Z = X ^ Y ^ Cin
Cout = ( X & Y ) | ( Cin & ( X ^ Y ) )

Then rearranging the first equation and substituting it into the second:

Cin = X ^ Y ^ Z
Cout = ( X & Y ) | ( ( X ^ Y ^ Z ) & ( X ^ Y ) )

Rather than reduce the Cout equation, it's easier to work out a truth table and then build up the final equation from that.

Note: I've tweaked both equations to remove unnecessary terms.

g3cwi · 2012-06-13 06:29

Hi again ericball

C would not have been my starting point for precedence as I have no knowledge of C. However, I might well have assumed that SPIN follows the BODMAS order but I will check. Thanks for the heads-up that SPIN (and C) might diverge from BODMAS.

Cheers

Richard

ericball · 2012-06-13 08:53

g3cwi wrote: »

C would not have been my starting point for precedence as I have no knowledge of C. However, I might well have assumed that SPIN follows the BODMAS order but I will check. Thanks for the heads-up that SPIN (and C) might diverge from BODMAS.

BODMAS (or PEDMAS/BEDMAS) doesn't include bit (AND/OR/XOR/NOT), shift, logical (AND/OR), or comparisons. SPIN puts the shifts and bit ops before multiplication, while C puts shifts after addition (so A << 2 + 1 becomes A << 3) and bit ops after comparisons (so A & 1 == 0 becomes A & FALSE ).

Phil Pilgrim (PhiPi) · 2012-06-13 10:30

I believe this method for addition will also work:

zlsb = xlsb + ylsb
zmsb = xmsb + ymsb - (zlsb ^ $8000_0000 < xlsb ^ $8000_0000)

I initially thought it was necessary to do an unsigned compare of zlsb with both xlsb and ylsb. But that appears not to be the case since, if a carry occurs, the sum will be less than each operand.

-Phil

g3cwi · 2012-06-13 10:38

I have deconstructed ericball's add to give:

pub main | t1,t2, t3, t4, t5
DEBUG.start(15,9600,4)
DEBUG.cls
DEBUG.Backlight (TRUE)
DEBUG.str(string("TEST ADD"))
DEBUG.nl

xmsb := ymsb:= 0
xlsb := 1 << 31
ylsb := 1 << 31
zlsb := xlsb + ylsb

t1 := xlsb | ylsb
t2 := xlsb & ylsb
t3 := !zlsb 
t4 := t1 & t3
t5 := t4 | t2

DEBUG.bin(t5, 32)
 
zmsb := xmsb + ymsb + t5 >> 31 



repeat

Still no idea how it works though...

'tis powerful magic indeed.

Cheers

Richard

jmg · 2012-06-13 12:42

ericball wrote: »

Look Ma, no IFs:

So how do the two form choices differ in size and speed ?

Some languages allow you to test the Carry Flag, or do in-line ASM of small code slices.

g3cwi · 2012-06-13 13:44

...are there any recommended books that deal with bit maths in the context of embedded programming? I would like to learn how some of these more advanced bitwise manipulations work. Looking around on the web has not revealed much.

Cheers

Richard

jmg · 2012-06-13 14:20

g3cwi wrote: »

...are there any recommended books that deal with bit maths in the context of embedded programming? I would like to learn how some of these more advanced bitwise manipulations work. Looking around on the web has not revealed much.

You could try a good calculator ?

I've found this one great
http://www.zoesoft.com/console-calculator/ccalc-downloads/

So if we take Phil's example from above, in CCalc syntax it is

 xlsb=0x99912345;ylsb=0x99954321;xmsb=0x2;ymsb=1;
 zlsb = (xlsb + ylsb) & 0xffffffff;GotCy=( (xlsb + ylsb) > 0xffffffff)

GotCy = 0x0001

PhiCY =-((zlsb @ 0x80000000) < (xlsb @ 0x80000000))
PhiCY = 0x0000

- but maybe my quick syntax morph lost something ?
CClac appears almost as a Text Editor, so you can copy/paste, and ; separates items on one line.
It allows named variables, and functions, and returns a Boolean 1/0 for <, >, =, tests
You can easily add checks, like the GotCy above.

and I think here I have correctly syntax--morphed
#12: [ zmsb = xmsb + ymsb + ((xlsb | ylsb) & !zlsb | xlsb & ylsb ) >> 31 ]

  xlsb=0x12345;ylsb=0x54321;xmsb=0x2;ymsb=1;
  zlsb = (xlsb + ylsb) & 0xffffffff;GotCy=( (xlsb + ylsb) > 0xffffffff)
GotCy = 0x0000
  EricCY = ((xlsb | ylsb) & (zlsb @ 0xffffffff) | (xlsb & ylsb) ) >> 31
EricCY = 0x0000

  xlsb=0x99912345;ylsb=0x99954321;xmsb=0x2;ymsb=1;
  zlsb = (xlsb + ylsb) & 0xffffffff;GotCy=( (xlsb + ylsb) > 0xffffffff)
GotCy = 0x0001
  EricCY = ((xlsb | ylsb) & (zlsb @ 0xffffffff) | (xlsb & ylsb) ) >> 31
EricCY = 0x0001

Or I might prefer the cleaner first define a user function pathway 
   NOT(v)=(v @ 0xffffffff)
NOT(v)=(v@0xffffffff)

and now we can write 
  EricCY = ((xlsb | ylsb) & NOT(zlsb) | (xlsb & ylsb) ) >> 31
EricCY = 0x0001

g3cwi · 2012-06-13 14:26

Thanks jmg. I can work through the algorithms and get the answers. What I can't do is understand why the algorithms give the answers. I want to understand the underlying maths a bit better. Might one of Knuth's books help?

Cheers

Richard

jmg · 2012-06-13 14:46

g3cwi wrote: »

Thanks jmg. I can work through the algorithms and get the answers. What I can't do is understand why the algorithms give the answers. I want to understand the underlying maths a bit better. Might one of Knuth's books help?

I tend to work like Eric commented in #18, which is jump to a truth table, once you have it reduced to a small instance
Here we are looking for a carry, which has only 2 feed-bits, for 4 possible choices.

Then the important bit is confirming what you think is needed, actually works.
CCalc can display in Dec/Hex/Bin, so you can see how the underlying maths works.

What might confuse with these examples, is the trick of using zlsb to derive the carry, as it is not a pure input variable,
but it is the sum of the two variables. ( and must of course be computed first )

Phil Pilgrim (PhiPi) · 2012-06-13 14:59

The "why" of my routine is pretty simple:

1. When there's a carry out of the sum, the sum itself, treated as an unsigned number, will be less than each of the operands, treated as unsigned numbers.
2. Spin uses only signed math, so the smallest number is $8000_0000 == -2_147_483_648, and the largest number is $7FFF_FFFF == 2_147_483_647.
3. To make an unsigned comparison using signed math, all you have to do is flip the sign bits of the operands, i.e. XOR with $8000_0000. This converts 0 to $8000_0000, the lowest signed number, and $FFFF_FFFF to $7FFF_FFFF, the highest signed number.
4. The comparison operators return -1 for true and 0 for false.
5. So if zlsb < xlsb (unsigned), there was a carry, and the expression returns -1; otherwise, 0.
6. Subtracting the result of the compare from the upper sum, therefore, is the same as adding 1 if there was a carry out of the lower sum; 0, otherwise.

-Phil

max72 · 2012-06-13 16:18

jmg wrote: »

Some languages allow you to test the Carry Flag, or do in-line ASM of small code slices.

There are at least two options for the propeller:
SpinLMM (you need bst), and the inline pasm by Beau (requires an extra cog).
Massimo

50 bit maths

Comments