Adam Berent wrote: > > Thank you for all your replies. > > I have looked at the gnu math libraries and frankly they make me want to blow my brains out. There are about a hundred source files. I don't even know where too start. Anyways I found another free math library called FreeLIP. It only has 4 source file 2 of which are .h files. This makes it possible to learn it in a reasonable period of time. > > However I would like to know what the trick is. Some people suggested storing the numbers in a string. This seems a bit crude and would probably be too slow. Does anyone know how these libraries work, at least in theory. I suspect the large numbers get broken down or factored into smaller ones. On the other hand factoring is also slow. Please give me a hint :) OpenSSL stores numbers in an array of the largest thing it can do efficient integer arithmetic on. For modern platforms this typically means 32 or 64 bit integers. It then does arithmetic the long way in base 2^32 or 2^64. This is interesting in itself, because some of the fast arithmetic algorithms have special exceptions for digits that are one less than the base, which in base 10 would be 9, of course, but in base 32 is 32 1s in a row - we had a bug in OpenSSL to do with one of these exceptions that went undetected for years (in fact until NIST released a large prime which had many long strings of 1s in it). BTW, multiplication is often done fast using a trick called "Montgomery multiplication", which is horribly complicated and involves storing the number in a very weird format. Cheers, Ben. -- http://www.apache-ssl.org/ben.html "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff
This archive was generated by hypermail 2b30 : Thu May 03 2001 - 14:35:08 PDT