128-bit Ints

[degibson]

I'm looking around for a simple, tight, header-only implementation of a 128-bit (unsigned or signed) integer in C++. Ideally, it would work in VC++ and G++.

Does anyone have pointer to something more minimal than GMP or http://mattmccutchen.net/bigint/ ?

Preferably, this will include a sqrt()-like functionality.

 

[Cogman]

It is non-standard, but a long long is a 128 bit integer.

As for sqrt like functionality, I'm not sure if there is a standard sqrt function for it. If you need to implement one, newtons method makes for a quick sqrt method that isn't too hard to implement.

 

[degibson]

It is non-standard, but a long long is a 128 bit integer.

hms-victory(1)% vim foo.C
  1 #include <iostream>
  2 #include <string>
  3 
  4 using namespace std;
  5 
  6 int main() {
  7   cout << sizeof(long long) << endl;
  8 }

hms-victory(2)% g++ foo.C
hms-victory(3)% ./a.out
8

Just eight bytes, unfortunately.
'long long long' is 'too long' for gcc

As for sqrt like functionality, I'm not sure if there is a standard sqrt function for it. If you need to implement one, newtons method makes for a quick sqrt method that isn't too hard to implement.

Yes, while I hold out some faith that I will find a nice header-only BigNum, I doubt it will have a 128-bit square root.

 

[Ken g6]

Hm, inside Jason Papadopoulos' MSieve, there's a 17K mp.h, but also a 35K mp.c. It's C, not C++, but it doesn't look too complicated, it does have a square root, and it's public domain.

Considering the differences between C and x86 assembly, you can either have an assembly implementation or a slow implementation.

 

[Cogman]

Well, your other option, then, is to do the MS cop-out and use something to the effect of a LARGE_INTEGER struct with a high and low long-long part. You'll have to do the nitty gritty of addition, subtraction, multiplication, ect (this is actually something that is easier to do in assembly then it is in C/C++, go figure)

 

[Schmide]

I'm just curious, have you thought of using floating point and designing your algorithms to compute a desired level of precision?

 

[degibson]

Hm, inside Jason Papadopoulos' MSieve, there's a 17K mp.h, but also a 35K mp.c...

Thanks for the additional link. If push comes to shove, I will consider a generic bignum library.

Considering the differences between C and x86 assembly, you can either have an assembly implementation or a slow implementation.

Yes, I'm worried about that as well. Ideally, I would have a header implementation consisting of inlined x86 ASM (thankfully, I don't need this code to run on SPARC).

Well, your other option, then, is to do the MS cop-out and use something to the effect of a LARGE_INTEGER struct with a high and low long-long part. You'll have to do the nitty gritty of addition, subtraction, multiplication, ect (this is actually something that is easier to do in assembly then it is in C/C++, go figure)

If I'm going to cop out and go with a struct, I'm at least going to find one for which I don't have to write my own mutators. Its not that I can't do it, its just that I would screw up corner cases on the first hash.

I'm just curious, have you thought of using floating point and designing your algorithms to compute a desired level of precision?

That's a possibility, but it's a comparable amount of detail to coding my own 128-bit integer.