I was thinking it would be fun to do some math with really big integers. Is FPU the best way to do it? How big integer values can FPU handle?
The FPU is notoriously bad for dealing with integers; some (whole) integer values cannot even be represented by the FPU! I can't remember the FPU limits off the top of my head, but it shouldn't be too hard to google :)
If you want to deal with really big integers ("bignums", as they're usually called), you'll want to use ALU and not FPU routines. There's several existing packages around, most well-known probably being MIRACL and GNU GMP.
If you want to deal with really big integers ("bignums", as they're usually called), you'll want to use ALU and not FPU routines. There's several existing packages around, most well-known probably being MIRACL and GNU GMP.
I won't probably use those packages because I want to code my own routines. Maybe my routines won't be as effective as in those packages, but it doesn't matter at this point. I think it won't be too hard to implement some basic mathematical functions. Some more complicated mathematical functions might need a little bit more thinking, but that won't be a problem.
You'll want to use some decent algorithms though, and there might be references in those packages. Addition is easy enough, but what do you do for multiplication? :)
How big integer values can FPU handle?
The FPU can correctly handle 64 bit signed integers.
You wouldn't usually try to use the FPU for more bits because it doesn't have the easy access to the flags you need to handle multiprecision arithmetic.
Paul.
f0dder, actually multiplication is easy, but not division. I haven't gotten myself to sit down to code a division routine, though I already have a multiplication version.
i guess the best way (well, not really best, but easy and good enougth) to do a multiplication with bignums is making it as you do with paper and pencil
ancev
ancev
As ancev suggested, the easiest way is to do it as you would with pencil and paper. However, if you do it in binary, resulting answers won't make much sense unless you convert them to the decimal system, which adds one more complicated step to the process.
You may thus want to do it in the decimal system to start with and avoid the complex conversion from binary. If you are not yet familiar with the BCD (Binary Coded Decimals) instructions, you may want to have a peek at the following:
http://www.ray.masmcode.com/BCDtut.html
Have fun
Raymond
You may thus want to do it in the decimal system to start with and avoid the complex conversion from binary. If you are not yet familiar with the BCD (Binary Coded Decimals) instructions, you may want to have a peek at the following:
http://www.ray.masmcode.com/BCDtut.html
Have fun
Raymond
let me say a few words...i've coded all that stuff in asm...including some things
that are unique (like montgomery modular exponentation, yes, in asm)
for division use "binary long division".
we, assembly programers, make a good use of BT,BTS instructions whereas C/C++ programers (f0dder :) ) have to put MORE lines of code to achieve this :O
Some good books:
A Computational Introduction to Number Theory and Algebra - Victor Shoup (IMO, A very good book!)
Art of Computer Programming Knuth vol v2 - D. E. Knuth (The mother, you'll see this book referenced in almost all papers)
Handbook of Applied Cryptography - A. Menezes, P. van Oorschot, and S. Vanstone (Chapter 14)
Multiple-length Division Revisited: a Tour of the Minefield - Brinch Hansen
also this excellent site (on other stuff too), that i found by searching, here:
http://www2.ics.hawaii.edu/~wes -- you'll want to read ICS623 Notes
it has some ASM too :)
that are unique (like montgomery modular exponentation, yes, in asm)
for division use "binary long division".
we, assembly programers, make a good use of BT,BTS instructions whereas C/C++ programers (f0dder :) ) have to put MORE lines of code to achieve this :O
Some good books:
A Computational Introduction to Number Theory and Algebra - Victor Shoup (IMO, A very good book!)
Art of Computer Programming Knuth vol v2 - D. E. Knuth (The mother, you'll see this book referenced in almost all papers)
Handbook of Applied Cryptography - A. Menezes, P. van Oorschot, and S. Vanstone (Chapter 14)
Multiple-length Division Revisited: a Tour of the Minefield - Brinch Hansen
also this excellent site (on other stuff too), that i found by searching, here:
http://www2.ics.hawaii.edu/~wes -- you'll want to read ICS623 Notes
it has some ASM too :)
I was thinking it would be fun to do some math with really big integers. Is FPU the best way to do it? How big integer values can FPU handle?
Check out the chapter on extended precision arithmetic in "The Art of Assembly Language Programming" at http://webster.cs.ucr.edu.
And the HLA standard library (also at the address above) contains lots of 64-bit and 128-bit arithmetic and logical routines.
Cheers,
Randy Hyde