Numbers bigger than memory
Pi
juanpide at gmail.com
Wed Dec 19 12:24:24 CET 2012
I'm sorry, but it's just a generic idea.
On the other hand I found a way to solve that kind of hyperpowers, but it
only works sometimes.
We have to work recurrently,using the relation:
a^i=a^j (mod m) <-> i=j (mod e)
to reduce the exponent.
where e = ordm(a) is the multiplicative order,
Thus, e is the minimum k that makes a^k=1 (mod m).
But it's only true if gcd(a,m)=1
cheers
2012/12/19 <bodrato at mail.dm.unipi.it>
> Ciao!
>
> Il Mar, 18 Dicembre 2012 4:23 am, Pi ha scritto:
> > I was trying to compute hyperpowers, such as 8^7^6^5^4^3^2, or 7^^7, in
> > order to further perform operations such as modular arithmetic. And I've
>
> I can suggest http://gmplib.org/manual/Integer-Exponentiation.html .
>
> I'd not use GMP to choose which one (8^7^..., or 7^^7) is even and which
> one is odd ;-)
>
> > It would be nice that GMP could be able to use numbers larger than
> memory.
> > Maybe using ...
> > ...some fast in-memory compression algorithms.
>
> I fear it wouldn't work for general numbers.
>
> If the programmer knows that she can expect some redundancy in the numbers
> used, she should exploit it. The library can not assume (nor verify) that
> numbers can be compressed.
>
> > ... being able to work directly with disk databases.
> > or even
> > ... allowing distributed computation.
>
> It can be nice.
> Do you have suggestions to obtain this goals with portable code?
>
> Regards,
> Marco
>
> --
> http://bodrato.it/papers/
>
>
More information about the gmp-discuss
mailing list