Re: [TCLCORE] TIP #237: Arbitrary-Precision Integers for Tcl

[Lars <Lar...@ma...>]

At 11.00 +0100 2005-01-17, Kevin B. Kenny wrote:
> TIP #237: ARBITRARY-PRECISION INTEGERS FOR TCL

/=C4ntligen!/

(For those of you not familar with Swedish, this translates to "at last".
It is also the cheer that now traditionally greet each new anouncement of a
winner of the Nobel Prize in literature.)

>    3. The /internalRep/ union in the /Tcl_Obj/ structure shall be
>       augmented with a /bignumRep/ field. This field shall be a
>       structure comprising a pointer and a long integer.

Perhaps it would be better to name it ptrAndLongRep or something similarly
generic? I suspect there could be other object types which would find a
pointer and an integer to be a useful form of internal representation.

>      The pointer
>       will designate an array of digits (the /dp/ member of an /mp_int/
>       structure in /libtommath/). The integer will be an encoding
>       comprising:
>
>                   * one bit representing the sign of the number
>
>                   * fifteen bits giving the size of allocated memory in
>                     the digit array.
>                   * fifteen bits giving the size
>                     of used memory in the digit array.
>
>       The reason for this tight encoding is that the size of a
>       /Tcl_Obj/ shall not change, and yet an /mp_int/ structure can be
>       stored in the internal representation. This encoding will allow
>       packing and unpacking the object with a few Boolean operations
>       and shifts rather than needing to use a pointer internal
>       representation and dynamically allocated memory to store the
>       /mp_int/. The drawback is that it is limited to integers of 2**15
>       digits (or 917,504 bits).

A quick calculation reveals that this amounts to 28 bits per digit. The TIP
should probably mention this (digit !=3D decimal or hex digit, but something
much larger), to put the matter in proportion for the reader.

A possible tweak could be to always allocate space for an even number of
digits, and discard bit 0 of that number, as it would be known anyway. Then
with 15 bits of allocated size one could employ 16 bits (32-1-15) for the
number of used digits, and increase the limit to 2**16.

>            * The binary '*' operator, if either argument is an
>              arbitary-precision integer, shall promote the other to an
>              arbitrary-precision integer. If both are native integers,
>              and /Tcl_WideInt/ is at least twice the width of a native
>              /long/, then the product will be computed in a
>              /Tcl_WideInt/,

Is there a point in continuing to speak of Tcl_WideInt here, or would "long
long" do just as well?

>            * The abs(), ceil(), double(), floor(), int(), round(),
>              sqrt(), and wide() math functions shall all be modified to
>              accept arbitrary-precision integers as parameters.

Would it make sense to introduce two new functions iceil() and ifloor()
(same as ceil() and floor(), but always returning integers) here? The only
reason I know of that it makes sense for a ceiling or floor operation to
return a float is that traditionally it would often not be possible to
represent the value as an integer, and with this TIP that problem
disappears.


>    8. The *format* and *scan* commands will acquire /D/, /O/ and /X/
>       specifiers

There is _already_ an %X [format] specifier. Also, what would be the
meaning of "converting to unsigned octal/hex", as the descriptions of %o
and %x currently say?
  http://www.tcl.tk/man/tcl8.5/TclCmd/format.htm#M14


> No reference implementation is present as yet; the plan is to develop
> it on the CVS branch called 'tcl-numerics-branch'. Vote will not be
> called until the implementation is far enough along to convince the Tcl
> Core Team that it is practicable in the 8.5 release schedule. (The
> author hopes to enlist other volunteers to assist with the effort.)

I'd love to help (although I fear my experience of actually writing C code
is a bit too small for me to actually be of much use).

Lars Hellstr=F6m