Re: tcl8.5: large float-value to very wide int ?

Kevin Kenny <kennykb@acm.org> wrote:
> We already have square-root-of-bignum in the library, but it's
> not exported. Primarily for reasons of controlling "code bloat",
> the bignum stuff hasn't introduced any new math functions.
> And sqrt() needs to preserve its old semantics, otherwise
> code that expects the result of sqrt(int) to be a floating point
> number will break rather badly.
Pity, but understandable...

> What I'm planning to do - in the fairly near future - is come
> up with an extension that can be [package require]d that adds
> the missing functionality:
> - direct base64 and base256 encoding/decoding of bignums

base256 would be "binary encoding", or something else ?

At the moment I was rather surprised, that specifying
a number as a decimal string appeared to be faster than
using [scan $hexstring %llx]. Are bignums internally
decimal-based, or is this just another "not-yet-optimised" ?

In my opinion, those (below) I marked with a (*) are
simple or common enough, to not have to require
package-requiring, those with (**) are deeper into
number-theory or computationally more complex, so
having to package.require them is fine:

> - greatest common divisor, least common multiple,
> extended Euclid algorithm
cool. (*)
I'm not sure about the "extended Euclid algorithm":
  If it is not a means to do gcd&lcm, I'd say: (**)

> - integer square (squaring is faster than multiplying)
> and square root
Extra function for squaring? Couldn't that be just an internal
optimization of "$bignum**2" ?
Integer-squareroot: cool (*) (suggestion for name: isqrt)

> - modular inverse
> - modular exponentiation
In my eyes this is really advanced stuff ... (**)

> - Legendre-Jacobi symbol
Isn't "==" just that?

> - primality testing
(**)
Since it may take a loooooong time for certain arguments,
it is perhaps better to do this outside of expr. Then it
could also be event-loop-compatible...

> - random prime generation
(**)
> - Possibly, optimizations for reduction by fixed moduli
> (Barrett, Montgomery, diminished-radix)
(**) or (*) depending on the "code-bloat" this would really cause.

> Is there anything obvious missing from this list that would
> be needed for your application?
For my "application", all I actually need (and what isn't already
there) is:
  isqrt,
  faster conversion (if internally appropriate) from/to
     (big-endian)binary(base=256),bin(base=2),hex strings.

> If, in the meantime, you need a better square root urgently,
> the double-precision square root followed by a couple of rounds
> of Newton-Raphson ought to work. (Ugly, I know, but I haven't
> anything better to offer just at the moment.)

I currently use external program "dc" for square-rooting.
on my maschine it takes about 4 milliseconds per call.
calling out to "dc" and having it return the original
number takes about 2 milliseconds, so I'm looking forward
to how long a builtin isqrt would take. I'd be very surprised,
if Newton-Raphson implemented in pure Tcl could compete with
calling out to bc...
Btw. having dc return a hex-number and then [scan ... %llx] takes
6 millisecs, and having dc return base256-binary fails due
to non-binarysafe exec.
Received on Fri Dec 23 18:58:38 2005