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$
2
  • 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, 2019 at 22:17
  • $\begingroup$ @AHusain Yes, that's a reasonable answer. $\endgroup$ Jan 4, 2019 at 2:20

3 Answers 3

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$
1
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$
3
  • $\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$ Jan 4, 2019 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, 2019 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$ Jan 4, 2019 at 22:15
0
$\begingroup$

Q# now has a BigInt type included: https://docs.microsoft.com/en-us/quantum/user-guide/language/typesystem/#available-types

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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