3 ms·
You're right, they do handle numbers of millions bits long and rather billions. But a 64-bit architecture allows the CPU's MDR datapath to read numbers only 64-
by sgy 13y ago
You're right, they do handle numbers of millions bits long and rather billions. But a 64-bit architecture allows the CPU's MDR datapath to read numbers only 64-bit long at once.
My question is: what about the case when the number is longer by one bit, let's say? What's the best/most efficient way to handle it?
- tptacek 13y agoI don't understand this question. Isn't the answer you're looking for just "use a bignum library"?
- sgy 13y agoKind of. I'm looking for a manual and efficient implementation to handle that <=> The speed of arithmetic IS a limiting factor here.
- tptacek 13y agoSo you're just looking for comparative review of different bignum libraries? That shouldn't be too hard to find. Bignum performance is important for several applications, most notably public key cryptography. Here's a good sort of survey piece to read: https://www.imperialviolet.org/2010/12/04/ecc.html https://www.imperialviolet.org/2010/12/04/ecc.html You'll be particularly interested in the limb scheduling optimization, which is tailored to the processor.
- sgy 13y agoI'm into figuring out a fast, self-developed mechanism more than using libraries. But you absolutely got it: a solution when the number doesn't fit in a single CPU register. Great read by the way. Thank you.
- pbsd 13y agoGMP [1] is the canonical solution for this. It's very fast (at scale) and has bindings to every useful language out there. It's also not that bad for small arguments. If GMP is not suitable, you're probably doing something fairly unique. In that case, details matter, like language, architecture, etc. [1] https://gmplib.org/ https://gmplib.org/
- sgy 13y agoIt will be certainly useful to review. Thank you very much.
- pvg 13y agoMaybe the answer for 'a few bits over 64' is __int128_t that gcc and clang support. Emulated but probably as fast or faster than an arbitrary precision lib. Easier to try, too.