4
$\begingroup$

Shor's algorithm works with very large integers; larger than 64 bits. So the built-in 64-bit Int type is insufficient for doing the classical processing (e.g. computing the multipliers $b^{2^k} \pmod{N}$). Is there a big int type suitable for those purposes?

$\endgroup$
  • 1
    $\begingroup$ Are you okay with how to build it as a user defined type if there is not a built-in? $\endgroup$ – AHusain Jan 3 at 22:17
  • $\begingroup$ @AHusain Yes, that's a reasonable answer. $\endgroup$ – Craig Gidney Jan 4 at 2:20
6
$\begingroup$

There is none at the moment (as of version 0.3). We're working on adding it as a primitive type, hopefully it will be included in the next release.

$\endgroup$
2
$\begingroup$

In the meantime you could make

newtype LongInt = (Int,Int)

where (a,b) could represent the integer $(2^{64}*a)+(b+2^{63})$

The arithmetic operations for this would then be overridden so you define your own (a,b)*(c,d) that gives another LongInt but with potential for overflow. So if this could be wrapped in Maybe monad, that would be better.

Continue this way like "long long int" that are 4 times the length of a standard 16 bit int in C.

You could make a different choice of how you want to encode larger integers as combinations of Int if you want.

$\endgroup$
  • $\begingroup$ That pushes the problem back to 128 bits, but I want numbers with tens of thousands of bits. I suppose I could use Int[] instead of (Int,Int)... Is there no way to bring in .net's existing bigint type? $\endgroup$ – Craig Gidney Jan 4 at 13:43
  • $\begingroup$ You could also double the bit length 9 more times and get into the 10000s. But I don't know if you really want arbitrarily large (memory nonwithstanding) or just 10000s bit large. $\endgroup$ – AHusain Jan 4 at 19:37
  • $\begingroup$ I think by the 4th doubling I'd be well into "I'm going to have to use a code generator" territory. The benefit of using an array is that the amount of code doesn't grow with the desired size. $\endgroup$ – Craig Gidney Jan 4 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.