Big Integers

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
I am just another Code Monkey.

A determined coder can write COBOL programs in any language. -- Author unknown.

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
«1

Comments

  • 41 Comments sorted by Date Added Votes
  • Maybe some kind of encryption function ???

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

    Bean
    logo.png?91518163160380889
    Esterline Research & Design
    thitt@esterlineresearch.com

    We offer consulting on the following areas of expertise:
    Frequency Control - Micro-Controller/Processor Projects
    Test and Automation - General Programming and Coding
    Circuit Design - Board Layouts
  • evanhevanh Posts: 4,180
    edited August 20 Vote Up0Vote Down
    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
  • 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
    I am just another Code Monkey.

    A determined coder can write COBOL programs in any language. -- Author unknown.

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
  • 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.



  • 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.
  • 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.
  • 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.
  • Phil Pilgrim (PhiPi)Phil Pilgrim (PhiPi) Posts: 21,237
    edited August 21 Vote Up0Vote Down
    Oops! Wrong thread. Carry on ...
    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • Maybe Heater can demonstrate how to use an FFT to multiply large numbers in O(nlog(n)) time.
  • Schoenhage-Strassen multiplication is O(N log(N) log(log(N))) surely ;)
  • Heater.Heater. Posts: 19,725
    edited August 21 Vote Up0Vote Down
    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.

  • 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
    “Perfection is achieved not when there is nothing more to add, but when there is nothing left to take away. -Antoine de Saint-Exupery
  • 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
    Tulsa, OK

    My OBEX objects:
    AGEL: Another Google Earth Logger
    DHT11 Sensor

    I didn't do it... and I promise not to do it again!
  • 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



    I am just another Code Monkey.

    A determined coder can write COBOL programs in any language. -- Author unknown.

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
  • Thanks, Mike - I will try it (hopefully this week).

    Walter
    Tulsa, OK

    My OBEX objects:
    AGEL: Another Google Earth Logger
    DHT11 Sensor

    I didn't do it... and I promise not to do it again!
  • 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...

    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

    I am just another Code Monkey.

    A determined coder can write COBOL programs in any language. -- Author unknown.

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
  • 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
    Tulsa, OK

    My OBEX objects:
    AGEL: Another Google Earth Logger
    DHT11 Sensor

    I didn't do it... and I promise not to do it again!
  • Yes

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

    Mike
    I am just another Code Monkey.

    A determined coder can write COBOL programs in any language. -- Author unknown.

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
  • doing some try on decimal output myself, seems more memory intensive as I thought of.

    Have to rethink my current approach.

    Mike
    I am just another Code Monkey.

    A determined coder can write COBOL programs in any language. -- Author unknown.

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
  • 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
    Tulsa, OK

    My OBEX objects:
    AGEL: Another Google Earth Logger
    DHT11 Sensor

    I didn't do it... and I promise not to do it again!
  • 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
    I am just another Code Monkey.

    A determined coder can write COBOL programs in any language. -- Author unknown.

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
  • OK, here now V.1.2

    Much fun

    Mike
    I am just another Code Monkey.

    A determined coder can write COBOL programs in any language. -- Author unknown.

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
  • 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
    Tulsa, OK

    My OBEX objects:
    AGEL: Another Google Earth Logger
    DHT11 Sensor

    I didn't do it... and I promise not to do it again!
  • msrobotsmsrobots Posts: 1,686
    edited September 2 Vote Up0Vote Down
    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
    I am just another Code Monkey.

    A determined coder can write COBOL programs in any language. -- Author unknown.

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
  • Anyways, I found the error in Decimal Output.

    Attached now working V1.3

    Enjoy!

    Mike
    I am just another Code Monkey.

    A determined coder can write COBOL programs in any language. -- Author unknown.

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
  • 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.

    Tulsa, OK

    My OBEX objects:
    AGEL: Another Google Earth Logger
    DHT11 Sensor

    I didn't do it... and I promise not to do it again!
  • 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
    Tulsa, OK

    My OBEX objects:
    AGEL: Another Google Earth Logger
    DHT11 Sensor

    I didn't do it... and I promise not to do it again!
  • FWIW FullDuplexSerial has spin routines to output decimal values.
    My Prop boards: P8XBlade2, RamBlade, CpuBlade, TriBlade
    Prop OS (also see Sphinx, PropDos, PropCmd, Spinix)
    Website: www.clusos.com
    Prop Tools (Index) , Emulators (Index) , ZiCog (Z80)
  • 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


    I am just another Code Monkey.

    A determined coder can write COBOL programs in any language. -- Author unknown.

    The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this post are to be interpreted as described in RFC 2119.
  • 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!
    Tulsa, OK

    My OBEX objects:
    AGEL: Another Google Earth Logger
    DHT11 Sensor

    I didn't do it... and I promise not to do it again!
Sign In or Register to comment.