Big Integers
msrobots
Posts: 3,709
in Propeller 1
Every time I read the propeller manual, I sort of stumble over add and addx, sub and subx and so on. Every time I think I should do something with the extended integer math.
Since I couldn't decide on how long my integers should be, I thought to just define that at variable level and do the math with any count of longs per variable. This lead to a pointer style of variable definition. A variable for the math routines is the address of a two long pointer, containing the length of a memory block (in longs) as first long and the address of the memory block (in longs) as the second long.
This sounds expensive, two longs overhead for a variable, and maybe it is, on a P1 I could press that into one long, but since the goal is to do math with long memory blocks, saving a long per variable seems not so important.
Using pointers makes a lot of things possible, the content of any variable can be at any address in HUB, including the ROM. So one can add the sine table to the cosine table and write the result to HUB, for example.
All variables are long aligned and 'longs' long, so we can do 32-bit, 64-bit, 96-bit, 128-bit..... math. All routines are fine with different sized variables, so adding a 64-bit variable and a 32-bit variable is supported. Same goes for 1024-bit (32 long) or 524,288-bit (4096 long) variables or any other size fitting into HUB.
So the math routines can add, subtract, multiply and divide signed and unsigned multi-long variables as long as they fit into memory. Since I needed CMP, CMPS, SHL, RCL and RCR for multiply and divide, they are also available.
As usual I did this in PASM, and build some simple SPIN test around it while debugging. All test cases seem to work fine.
BUT, what to do with it?
This is a solution, searching for a problem to solve.
Entering two 524,288-bit (4096 long) variables in the serial terminal and viewing the result seems boring. And confirming the result is not easy.
I even have no idea for a demo, besides a simple calculator in the serial terminal.
any input welcome,
Mike
Since I couldn't decide on how long my integers should be, I thought to just define that at variable level and do the math with any count of longs per variable. This lead to a pointer style of variable definition. A variable for the math routines is the address of a two long pointer, containing the length of a memory block (in longs) as first long and the address of the memory block (in longs) as the second long.
This sounds expensive, two longs overhead for a variable, and maybe it is, on a P1 I could press that into one long, but since the goal is to do math with long memory blocks, saving a long per variable seems not so important.
Using pointers makes a lot of things possible, the content of any variable can be at any address in HUB, including the ROM. So one can add the sine table to the cosine table and write the result to HUB, for example.
All variables are long aligned and 'longs' long, so we can do 32-bit, 64-bit, 96-bit, 128-bit..... math. All routines are fine with different sized variables, so adding a 64-bit variable and a 32-bit variable is supported. Same goes for 1024-bit (32 long) or 524,288-bit (4096 long) variables or any other size fitting into HUB.
So the math routines can add, subtract, multiply and divide signed and unsigned multi-long variables as long as they fit into memory. Since I needed CMP, CMPS, SHL, RCL and RCR for multiply and divide, they are also available.
As usual I did this in PASM, and build some simple SPIN test around it while debugging. All test cases seem to work fine.
BUT, what to do with it?
This is a solution, searching for a problem to solve.
Entering two 524,288-bit (4096 long) variables in the serial terminal and viewing the result seems boring. And confirming the result is not easy.
I even have no idea for a demo, besides a simple calculator in the serial terminal.
any input welcome,
Mike
Comments
That's the only thing I can think of that would require more than 64 bit integers.
Bean
- Large area spacial simulators is one area but speed is somewhat nerf'd with the overwhelming amount of number crunching needed.
- Financial calculations is the other. The above works well for these as they aren't speed demons but absolute accuracy is important no mater how big the kitty is.
EDIT: typo
Try that with your pocket calculator...
Mike
A good test for large int arithmetic is to check by wooping.
Symbolic algebra packages need arbitrary precision integers for simplifying big expressions, for instance,
the intermediate results can be massively larger than the final result coefficients.
But the heater_fft is out there if anyone is weird enough to want to do that on a Prop.
-Phil
Many years ago I wrote an IBM 1130 assembler program that computed e to 1000 decimal places. In effect it used big integers.
If you would be kind enough to post your routines I could convert the program to Spin to test your routines.
Might not be practical, but I'm interested, at least.
Walter
I had to clean it up a bit, now I have some usable test program.
standard serial 115,200 - after start it waits for you to press 'THE ANY KEY' after opening your terminal program to start.
Mulx and Divx have undefined flags on exit, all other ones seem to fit.
give it a try ...
Mike
Walter
OK, I did some rework to make it more usable. please do not use the Archive of the last post, use the one here, marked a V.1.1
As mentioned in the first post I was unhappy with a 2 long variable descriptor, I was able to compress it down to 1 Long.
This removes a lot of RDlongs and makes the overall handling more easy.
A bigIntVariable is now just one long, 14 bits for size in longs and 18 bits for address in longs.
This allows to just move that one long around, instead of a pointer to a 2 long block.
A bigIntVariable can point to any long address in HUB and ROM on the P1, and can - theoretically - be at a address at 1MB on some - theoretically - P2.
The size of the memory block a bigIntVariable is pointing at can be one to $3FF (16383) Longs, and also enough for a - theoretically - P2.
On a P1 a sensible maximal usable size is around 1000 longs, for each of the Parameter, giving a result of 2000 longs using a workbuffer of 2000 Longs. That are 4000 Longs Hub-Ram.
And you can do math with 32,000 bits giving results of 64,000 bits. So not 1000 decimal places but 1000 longs...
Not bad for the P1.
I do have serial input of decimals and hex-numbers for bivariables, outputting hex-numbers is also there for any bivariable.
But decimal output gives me some headache, will ask in another thread.
So currently 115200 baud, no other pins involved as 30/31 run it on any Propeller, open the terminal and hit THE ANY KEY when ready.
Enjoy!
Mike
Is there some way to get the remainder from the division operator (or a modulo function)?
I can use the other functions to calculate the remainder if not.
This is so I can output the result value in decimal rather than hex.
Thanks
Walter
Result contains result of operation and workSpVar contains remainder (the 4. buffer)
Mike
Have to rethink my current approach.
Mike
... but I'm only using the add, multiply, and divide functions at this time.
A couple of comments... (I had time to kill while it computed) (interesting code!)
In the cmdmov routine, you do a cmp without setting any flags...
cmdmov mov resultlongs, wrkdes1 cmp resultlongs, wrkdes2 if_a mov resultlongs, wrkdes2 'copy smaller sizeWhich of course means the previous flag states are used when evaluating the if_a conditional.
There's also a few places like this code:
cmp resultdes, #0 WZ 'if result buffer lenght < 1 if_z jmp #endcommand 'doneWhich could be shortened to:
(I'm assuming you may need the Z flag to be set)
I'm going to continue to clean up my code. I do have a (very very very slow) decimal output routine. I think I may be able to speed it up a fair amount but have yet to try.
Thanks,
Walter
That tjz is new to me. Nice.
I have now decimal out running in spin, but needed more buffers so now I am down to max 500 longs before running out of hub-ram.
I need to do some cleanup in the code and will post the result later today.
But yes, my decimal output is also way slower then hex output.
Enjoy!
Mike
Much fun
Mike
Values such as 123, etc. display properly.
Values such as 10, 100, etc. are displayed as 1. It appears to be an issue when the remaining digits to be displayed are all zeroes.
Otherwise, the computations (add, multiply, divide) still look fine.
If you are interested, I might be able to shorten some of the code... especially since you're almost out of hub ram... be glad to help.
Thanks,
Walter
Decimal out is my second version, first one would not display zeroes at all...
I am not sure if using 2 extra buffer at this size are needed, it was sort of late.
and 12 * 500 longs are 6000 longs just for variables.
But sure, go ahead I wanted to stray away from it anyway and go over my g-code experiment. I usually run multiple projects, so I can let them sit while stuck somewhere and do something different, coming back with new eyes after some distraction.
Enjoy!
Mike
Attached now working V1.3
Enjoy!
Mike
And I also have multiple projects. I'm still working on my first propeller project from almost 8 years ago.
I have learned that there's almost always better ways to do something with a computer. We can all learn from each other, I've certainly learned some things from your code.
I'll apply my changes to v1.3 and get them to you.
I'm attaching my test code (which includes the changes I mentioned earlier).
bitest_e_1000 is my test routine:
InputSize and input/output types are still used, except that InputSize now determines (as a power of 2) the number of decimal digits (approximately) of e that are computed.
The calculation method is ignored.
The "1" values reported should be "1" followed by many zeros.
The "46" value reported at the end should be "460".
Please take all changes with a big grain of salt. Although they seem to work fine with my code they may certainly cause other issues. No harm is intended, just trying to help.
Thanks,
Walter
yes, but just one long, not say a number made out of 3 longs or 96 bits. or 500 longs and 16,000 bits.
Mike
I'll review and make changes as necessary.
Sorry for any confusion!