#41 Faster large integer->string conversion?

open
nobody
general (11)
5
2017-07-31
2010-01-14
No

I'm not sure if anything can be done, but the conversion from large integer to string
takes inordinately look. For example, I just computef fib(1000000) in 36 cpu seconds,
but the conversion of the ~209000 digit result to a string for output took well over
5 cpu *minutes*. Is that really necessary?

Discussion

  • Clinton Jeffery

    Clinton Jeffery - 2010-01-14

    I would welcome contributions from anyone who wishes to tune this operation.

     
  • Charles Evans

    Charles Evans - 2012-07-17

    libgmp10 would probably help if used for all largeints, especially on 32bit iconx?,
    but AFAIK exact conversion to decimal is extremely slow.
    I suggest a function that produces n correct digits then lots of 0's.
    I'm not sure how...

     
  • Charles Evans

    Charles Evans - 2017-06-06

    We need a way to use the new 128bit
    FPU's on the recent CPU's that have them.

    Just guessing, but libquadmath
    might help if it has int functions.
    Unfortunately Ubuntu Zesty has no
    -dev deb for it.

    Also notice that libgmp10 is not using
    LGPL2 but LGPL3, or GPL2.

    libgmp-dev is not compatible with
    libquadrule-dev on ubuntu zesty,
    you must use instead libgmpv4

    IIRC libboost-math-dev has c++ libs for
    very large int and dec_float types.

     
  • Clinton Jeffery

    Clinton Jeffery - 2017-06-06

    For what its worth, libGMP seems to outperform our "native" large integers on regular arithmetic operations, and I am contemplating an implementation of large integers to use libGMP. I don't know libquadmath so I don't know that it is needed, although the idea of an intermediate representation between 64-bit and arbitrary size is interesting: three integer representations?! Maybe not worth the code complexity unless it is a Lot faster than libGMP, and if 65-128 bit integers are reasonably common.

     
  • Charles Evans

    Charles Evans - 2017-06-06

    libquadmath has rounding to int,
    but no real int types AFAICT
    We could try the %G format to see
    if it will really sprintf a 100bit int.
    I think it will do about 30 digits,
    sadly not a full 128bit int.
    It should be incredibly fast up to 30 digits, but I have not yet tried it.

     
  • Charles Evans

    Charles Evans - 2017-06-06

    libgmp uses SSE2
    (on all Athlon64, >=2004, all Intel64? )
    We need to be sure we are using it
    (CFLAGS?). Is ubuntu .deb a fat binary?
    If so, Intel Broadwell+ should be faster, using ADX. Libs built with --enable-fat should use it automatically.
    Stack usage .5M
    Some BSD < v10 need older libgmp

    If libgmp is MUCH faster at 30 digits than at 45 digits, libquadmath is not worth checking IMHO.

    The libboost mailing lists discuss
    __int128, but I don't know if they
    have hardware support for multiprecision
    yet.

     
  • Charles Evans

    Charles Evans - 2017-06-10

    sse2 : 128bit int
    It looks like we should see more big gains with arrays of 128bit ints and libgmp if we do array ops
    (sse2 latency up to 5x throughput)

    Sandy Bridge and Bulldozer and later have AVX, 2011+
    256bit FP operands, 128bit int
    (Bulldozer 128bit FPU)

    AVX2: Haswell, Excavator: 256bit int
    when libgmp supports AVX2, we may want
    arrays of 256bit ints
    arrays of 128bit floats would be nice now, using libquadmath.

    libgmp also has decimal largeints,
    totally avoiding the extremely slow
    process of binary to string.
    The math itself may be noticeably slower.
    gnucobol uses libgmp for this.

    ubuntu: libgmp-dev now works with libquadrule-dev,
    now libgmpv4-dev is conflicting
    with libmpfi-dev and libmpfr-dev

     
  • Charles Evans

    Charles Evans - 2017-07-31

    Partial precision printing should be fast for integers up to 128bit using libquadmath:

    Convert to float128, sprintf, massage the string to look like an int.

    Larger ints could truncate low order ( x:=n-128) bits, convert to float128, multiply by real(2^x), then sprintf, etc. - still quite fast, orders of magnitude faster than exact printing.

     
    • Clinton Jeffery

      Clinton Jeffery - 2017-07-31

      I would welcome code that speeds us up with identical output to our current output. My main concern is usually portability, then speed. If libquadmath or libgmp come with Mingw64 on Windows and Xcode on Mac, that helps. Otherwise they are only a partial solution.

      I did hire a student to take preliminary steps toward a libGMP large integer implementation this summer. Results are not in yet. I expect garbage collection to be problematic.

       
  • Charles Evans

    Charles Evans - 2017-07-31

    Excellent! I look forward to testing it.

    I suppose that any approximate string
    would have to be a library function or a loadfunc() that one could use for dry-run rough-in testing code, not for actual production use.

     

Log in to post a comment.