ZZ for base more than 2^64

[Oleksandr Kazymyrov]

Dear all,

In manual "ZZ ?" you can find:

As an inverse to "digits()", lists of digits are accepted, provided

       that you give a base. The lists are interpreted in little-endian

       order, so that entry "i" of the list is the coefficient of

       "base^i":

    

          sage: Z([3, 7], 10)

          73

          sage: Z([3, 7], 9)

          66

          sage: Z([], 10)

          0

But for base more than 2^64 it doesn't work. It looks stupid, because you can call "digits(2^64)", but not an inverse function:

sage: a=ZZ(randint(0,2^128-1)).digits(2^64)

sage: a

[1154963902035838039, 8176620537326016718]

sage: ZZ(a,2^64)

ERROR: An unexpected error occurred while tokenizing input

The following traceback may be corrupted or invalid

The error message is: ('EOF in multi-line statement', (1348, 0))

---------------------------------------------------------------------------

OverflowError                             Traceback (most recent call last)

....

OverflowError: long int too large to convert

Of course it is possible to convert it back using Sage:

sage: a=ZZ(randint(0,2^128-1))                         

sage: a

201636464310824733716520014075404236490

sage: b=a.digits(2^64)

sage: b

[6699442741605840586, 10930734632904602844]

sage: sum([b[i]*(2^64)^i for i in xrange(len(b))]) == a

True

Why core library doesn't include this functionality? Are there any other ways to do the same as described above using another function?

'Sage Version 5.0, Release Date: 2012-05-14'

Linux hamsin 3.2.0-24-generic #38-Ubuntu SMP Tue May 1 16:21:07 UTC 2012 i686 i686 i386 GNU/Linux

[Keshav Kini]

Thank you for the report! This is now lucky ticket #13000 -
http://trac.sagemath.org/sage_trac/ticket/13000

-Keshav

----
Join us in #sagemath on irc.freenode.net !

[P Purkayastha]

 We have 13k bugs!

[Martin Albrecht]

It's easy: implement it and send us a patch ;) On a more serious note, it
seems you found a bug and your code above is the right fix. So it would be
great if you could open a ticket and provide a patch which falls back to the
generic code above if the base is >= 2^64.

Cheers,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinr...@jabber.ccc.de

[Keshav Kini]

Well, not really - IMO, the correct fix is what David Roe already
implemented at http://trac.sagemath.org/sage_trac/ticket/13000 . There's
already code in sage/rings/integer.pyx to handle large bases. The bug is
that the input is cast to unsigned int in all cases, instead of just in
the case that it is detected as being possible to do so. The patch fixes
it without resorting to fallbacks into generic Python, and actually
fixes the real bug.