Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re^3: Module for 128-bit integer math?

by salva (Abbot)
on Feb 06, 2011 at 17:21 UTC ( #886534=note: print w/replies, xml ) Need Help??


in reply to Re^2: Module for 128-bit integer math?
in thread Module for 128-bit integer math?

Or at least wrap one of the C libs that do it.

Have you found any 128bit math library in good shape? I have been googling for a while and all I have found is very rudimentary. Nothing complete or exploiting the 128bit abilities of modern processors.

gcc seems to have some basic support also, but the documentation about that feature is very poor and does not even state the processors where it is supported.

Well, the thing is that if you are able to find some good 128bits library, building a Math::Int128 module using Math::Int64 as a base should be pretty straight forward. Just point me to the library and I will do it!

BTW, I would also like to see a 256bits module... even if at that size, the performance would be pretty similar to that of a bigint library operating over integers of the same size.

Replies are listed 'Best First'.
Re^4: Module for 128-bit integer math?
by BrowserUk (Pope) on Feb 06, 2011 at 21:10 UTC
    Have you found any 128bit math library in good shape?

    No not yet. I assumed that they would exist, but so far all I've found is 128-bit FP and arbitrary precision integer:(

    building a Math::Int128 module using Math::Int64 as a base

    That was my thought also.

    Just point me to the library and I will do it!

    That's an offer I cannot pass up. Thank you.

    From what I've seen so far, I'll end up having to write the C library myself.


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      I have just uploaded Math::Int128 to CPAN (GitHub repository).

      It has to be compiled with the development version of GCC for its 128bit integer support.

      At this point, the module is completely experimental, has been only slightly tested (it has no tests, yet) and may contain lots of bugs, so, don't think about using it for anything serious!

        • Does int128() and uint128() croak for "0400000000000000000000000000000000000000"?
        • Does $x + undef and the like warn? (Note that «undef + $x» cannot warn without making «my $x; $x += int128(...)» warn.)
        • Does signed to unsigned promotion occur when required? (e.g. when adding two a large number overflows.)
        • Does unsigned to signed promotion occur when required? (e.g. when subtraction overflows to something negative.)
        • Are the string buffers always suitably aligned for a int128_t? (You use memcpy in some spots, but casts in others.)
        I have just uploaded Math::Int128 to CPAN

        Just tried building it using the mingw64 compiler, and it failed spectacularly. I speculate that this is a shortcoming of the compiler ... though it does have the 16 byte __int128 data type. However, the __int128 data type appears to be a signed value only.
        The "unsigned __int128" is, afaict, an unknown type and, I suspect, the cause of the errors reproduced below.

        Trying to determine sizeof(unsigned __int128) in a C program produces the compile-time error:
        expected ')' before '__int128'

        Salva, let me know if there's any point in following this further with that compiler, and I'll certainly try to work through it. Here's what I get when running dmake (x64 build of perl-5.12.0):
        C:\sis\Math-Int128-0.01>dmake test cp lib/Math/Int128.pm blib\lib\Math\Int128.pm C:\_64\perl512_M\bin\perl.exe C:\_64\perl512_M\lib\ExtUtils\xsubpp -t +ypemap C:\ _64\perl512_M\lib\ExtUtils\typemap Int128.xs > Int128.xsc && C:\_64\p +erl512_M\b in\perl.exe -MExtUtils::Command -e "mv" -- Int128.xsc Int128.c x86_64-w64-mingw32-gcc -c -I. -s -O2 -DWIN32 -DHAVE_DES_FCRYPT -DWIN +64 -DCONSE RVATIVE -DPERL_IMPLICIT_CONTEXT -DPERL_IMPLICIT_SYS -fno-strict-aliasi +ng -mms-bi tfields -DPERL_MSVCRT_READFIX -g -O0 -DVERSION=\"0.01\" -DXS_V +ERSION=\"0 .01\" "-IC:\_64\perl512_M\lib\CORE" Int128.c Int128.xs:15:27: error: expected '=', ',', ';', 'asm' or '__attribute_ +_' before 'uint128_t' Int128.xs:63:17: error: expected declaration specifiers or '...' befor +e 'uint128 _t' Int128.xs: In function 'newSVu128': Int128.xs:66:22: error: 'u128' undeclared (first use in this function) Int128.xs:66:22: note: each undeclared identifier is reported only onc +e for each function it appears in Int128.xs: At top level: Int128.xs:99:1: error: expected '=', ',', ';', 'asm' or '__attribute__ +' before ' atoa128' Int128.xs:169:1: error: expected '=', ',', ';', 'asm' or '__attribute_ +_' before 'SvU128' Int128.xs: In function 'su128_to_number': Int128.xs:210:5: error: 'uint128_t' undeclared (first use in this func +tion) Int128.xs:210:15: error: expected ';' before 'u128' Int128.xs:212:10: error: 'u128' undeclared (first use in this function +) Int128.xs: At top level: Int128.xs:221:26: error: expected ')' before 'u128' Int128.xs:247:23: error: expected ')' before 'i128' Int128.xs: In function 'XS_Math__Int128_uint128': Int128.xs:274:5: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__Int128_net_to_uint128': Int128.xs:333:55: error: 'uint128_t' undeclared (first use in this fun +ction) Int128.xs:333:65: error: expected ')' before 'pv' Int128.xs:334:65: error: expected ')' before 'pv' Int128.xs:335:63: error: expected ')' before 'pv' Int128.xs:336:61: error: expected ')' before 'pv' Int128.xs:337:59: error: expected ')' before 'pv' Int128.xs:338:57: error: expected ')' before 'pv' Int128.xs:339:55: error: expected ')' before 'pv' Int128.xs:340:53: error: expected ')' before 'pv' Int128.xs:341:51: error: expected ')' before 'pv' Int128.xs:342:49: error: expected ')' before 'pv' Int128.xs:343:47: error: expected ')' before 'pv' Int128.xs:344:45: error: expected ')' before 'pv' Int128.xs:345:43: error: expected ')' before 'pv' Int128.xs:346:41: error: expected ')' before 'pv' Int128.xs:347:39: error: expected ')' before 'pv' Int128.xs:348:37: error: expected ')' before 'pv' Int128.xs:348:37: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__Int128_uint128_to_net': Int128.xs:375:5: error: 'uint128_t' undeclared (first use in this func +tion) Int128.xs:375:15: error: expected ';' before 'u128' Int128.xs:383:36: error: 'u128' undeclared (first use in this function +) Int128.xs: In function 'XS_Math__Int128_native_to_uint128': Int128.xs:411:5: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__Int128_uint128_to_native': Int128.xs:437:5: error: 'uint128_t' undeclared (first use in this func +tion) Int128.xs:437:15: error: expected ';' before 'u128' Int128.xs:443:5: error: 'u128' undeclared (first use in this function) Int128.xs: In function 'XS_Math__Int128_uint128_to_hex': Int128.xs:453:5: error: 'uint128_t' undeclared (first use in this func +tion) Int128.xs:453:15: error: expected ';' before 'u128' Int128.xs:459:17: error: 'u128' undeclared (first use in this function +) Int128.xs: In function 'XS_Math__Int128__left': Int128.xs:623:9: error: 'uint128_t' undeclared (first use in this func +tion) Int128.xs:623:19: error: expected ';' before 'b' Int128.xs:626:13: error: 'b' undeclared (first use in this function) Int128.xs:635:19: error: expected ';' before 'b' Int128.xs: In function 'XS_Math__Int128__right': Int128.xs:652:9: error: 'uint128_t' undeclared (first use in this func +tion) Int128.xs:652:19: error: expected ';' before 'b' Int128.xs:655:13: error: 'b' undeclared (first use in this function) Int128.xs:664:19: error: expected ';' before 'b' Int128.xs: In function 'XS_Math__UInt128__add': Int128.xs:938:9: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__UInt128__sub': Int128.xs:957:27: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__UInt128__mul': Int128.xs:973:9: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__UInt128__div': Int128.xs:988:5: error: 'uint128_t' undeclared (first use in this func +tion) Int128.xs:988:15: error: expected ';' before 'up' Int128.xs:989:15: error: expected ';' before 'down' Int128.xs:993:13: error: 'up' undeclared (first use in this function) Int128.xs:994:13: error: 'down' undeclared (first use in this function +) Int128.xs:1002:9: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__UInt128__remainder': Int128.xs:1021:5: error: 'uint128_t' undeclared (first use in this fun +ction) Int128.xs:1021:15: error: expected ';' before 'up' Int128.xs:1022:15: error: expected ';' before 'down' Int128.xs:1026:13: error: 'up' undeclared (first use in this function) Int128.xs:1027:13: error: 'down' undeclared (first use in this functio +n) Int128.xs:1035:9: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__UInt128__left': Int128.xs:1054:9: error: 'uint128_t' undeclared (first use in this fun +ction) Int128.xs:1054:19: error: expected ';' before 'a' Int128.xs:1056:13: error: 'a' undeclared (first use in this function) Int128.xs:1057:13: error: 'b' undeclared (first use in this function) Int128.xs:1063:9: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__UInt128__right': Int128.xs:1082:9: error: 'uint128_t' undeclared (first use in this fun +ction) Int128.xs:1082:19: error: expected ';' before 'a' Int128.xs:1084:13: error: 'a' undeclared (first use in this function) Int128.xs:1085:13: error: 'b' undeclared (first use in this function) Int128.xs:1091:9: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs:1094:19: error: expected ';' before 'b' Int128.xs: In function 'XS_Math__UInt128__spaceship': Int128.xs:1111:5: error: 'uint128_t' undeclared (first use in this fun +ction) Int128.xs:1111:15: error: expected ';' before 'left' Int128.xs:1112:15: error: expected ';' before 'right' Int128.xs:1115:9: error: 'left' undeclared (first use in this function +) Int128.xs:1116:9: error: 'right' undeclared (first use in this functio +n) Int128.xs: In function 'XS_Math__UInt128__and': Int128.xs:1209:9: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__UInt128__or': Int128.xs:1225:9: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__UInt128__xor': Int128.xs:1241:9: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__UInt128__bnot': Int128.xs:1266:5: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__UInt128__neg': Int128.xs:1276:5: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here Int128.xs: In function 'XS_Math__UInt128__clone': Int128.xs:1306:5: error: too many arguments to function 'newSVu128' Int128.xs:63:1: note: declared here dmake: Error code 129, while making 'Int128.o'
        Cheers,
        Rob

        Wow! That was fast!

        Unfortunately, I don't think I'll be able to make use of it :(

        Whilst I have MinGW for 32-bit setup and working, I've never succeeded in getting a 64-bit version to work in conjunction with my 64-perl. And I need this to work there.

        I will download it and see if I can build it for 32-bit, but it won't be for a couple of days as I'm out tomorrow. I'll also try to knock up a test script, though it won't use Test::*. For this kind of thing I favour a random testing mechanism. Eg. generate a couple of numbers; multiply them; divide the results by one of them and check that result matches the other. Similarly for add/subract, shift-left/right etc.

        I've started to develop a my own using MSC and a struct containing two 64-bit ints. Add/subtract and multiply work--albeit that the latter uses a slow algorithm. I'm a bit hung up on div/mod at the moment.

        For a first pass I'm doing this using standard C math. In theory, it should be quicker using the 128-bit XMM registers, but the docs for the SSE/SSE2/SSE3 et al. intrinsics are less than detailed. Counter to my understanding earlier in this thread, those instructions don't support 128-bit math directly. They do support SIMD operations on pairs of 64-bit ints/uints, which in theory should speed up multiplication/division no end, but the combinations of incantations required are not at all clear. I've failed completely to turn up any examples on the web.

        Maybe if I can get it something to fly here, we could look at adding it to your module; or making a Win module that yours can defer to on this platform?

        One thing that might be useful to me if you have the time, is an assembler dump of the sources. Can gcc do that? And if it can, would it show the actual operations involved, or just calls to system library routines? Are they inlined?


        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://886534]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (3)
As of 2020-09-19 22:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    If at first I donít succeed, I Ö










    Results (116 votes). Check out past polls.

    Notices?