# Big Integers

Posts: 3,310
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
«1

• Posts: 8,121
Maybe some kind of encryption function ???

That's the only thing I can think of that would require more than 64 bit integers.

Bean
• Posts: 10,242
edited 2017-08-20 04:27
A couple of serious uses are well known for needing simultaneously large and precise dynamic range:

- 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
• Posts: 3,310
Financial calculations. Yay, I could divide the current public debt by the number of people living in the US.

Try that with your pocket calculator...

Mike
• Posts: 21,233
msrobots,
And confirming the result is not easy.
Sure it is. Just do the same calculation with Python. Python can deal with huge integers with ease.

• Posts: 957
Heater. wrote: »
msrobots,
And confirming the result is not easy.
Sure it is. Just do the same calculation with Python. Python can deal with huge integers with ease.
And pySerial can interface to the serial port. So it can be automated.
• Posts: 1,981
Financial calculations are often done in base 10 I believe (ie BCD or as ASCII digit string).

A good test for large int arithmetic is to check by wooping.
• Posts: 1,981
That's the only thing I can think of that would require more than 64 bit integers.

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.
• Posts: 22,860
edited 2017-08-21 22:00
Oops! Wrong thread. Carry on ...
• Posts: 957
Maybe Heater can demonstrate how to use an FFT to multiply large numbers in O(nlog(n)) time.
• Posts: 1,981
Schoenhage-Strassen multiplication is O(N log(N) log(log(N))) surely
• Posts: 21,233
edited 2017-08-21 23:51
No. I thought about playing with FFT multiplication ages ago. Seemed like such a weird thing it had to be tried. Never happened. The moment has gone.

But the heater_fft is out there if anyone is weird enough to want to do that on a Prop.

• Posts: 22,860
heater wrote:
But the heater_fft is out there if anyone is weird enough to want to do that on a Prop.
I totally misread that the first time as, "But the heater_fft is out there if anyone is weird enough to want to do that to a Prop."

-Phil
• Posts: 389
Mike,

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
• Posts: 3,310
wmosscrop wrote: »
Mike,

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

• Posts: 389
Thanks, Mike - I will try it (hopefully this week).

Walter
• Posts: 3,310
wmosscrop wrote: »
Thanks, Mike - I will try it (hopefully this week).
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...

I do have serial input of decimals and hex-numbers for bivariables, outputting hex-numbers is also there for any bivariable.

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

• Posts: 389
I'm taking a look at it now.

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
• Posts: 3,310
Yes

Result contains result of operation and workSpVar contains remainder (the 4. buffer)

Mike
• Posts: 3,310
doing some try on decimal output myself, seems more memory intensive as I thought of.

Have to rethink my current approach.

Mike
• Posts: 389
I've got my program mostly converted over to your routines. I found no problems with the results...

... 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 size
``````

Which 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                                     'done
``````

Which could be shortened to:
``````                        tjz     resultdes, #endcommand WZ
``````

(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
• Posts: 3,310
Well the missing WZ is a oversight I tend to do often.

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
• Posts: 3,310
OK, here now V.1.2

Much fun

Mike
• Posts: 389
There appears to be an issue with your decimal output routine.

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
• Posts: 3,310
edited 2017-09-02 00:55
sure, this is just a programming exercise, because I need distraction from my day-job.

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
• Posts: 3,310
Anyways, I found the error in Decimal Output.

Attached now working V1.3

Enjoy!

Mike
• Posts: 389
It seems like everything I do is a distraction from my day job...

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.

• Posts: 389
Still doesn't output decimal values correctly.

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
• Posts: 17,190
FWIW FullDuplexSerial has spin routines to output decimal values.
• Posts: 3,310
Cluso99 wrote: »
FWIW FullDuplexSerial has spin routines to output decimal values.

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

• Posts: 389
Where I was trying to set (or reset) the carry flag, I may not have used the proper instructions.

I'll review and make changes as necessary.

Sorry for any confusion!