02-27-2019, 03:28 PM
I am not sure about HP Prime, but XCas 1.4.9-57(win32) had a matrix power 31 bits limit.
Example: Perrin Primality test
qpowmod(n) := ([[0,1,1],[1,0,0],[0,1,0]] % n) ^ (n-1)
perrin(n) := dot(qpowmod(n)(2), [2,0,3]) == 0
map(range(2, 10), x -> x * perrin(x)) ==> [2, 3, 0, 5, 0, 7, 0, 0]
However, the code will not work for n > 2^31
perrin(9876543211) ==> "Abs Error: Bad Argument Type"
To fix it, need another matpow version that can handle bigger n:
matpow2hlp(a, n, half) := ifte(odd(n), a*half, half) * half
matpow2(a, n) := ifte(n<2^31, a^n, matpow2hlp(a, n, matpow2(a, n div 2)))
qpowmod2(n) := matpow2([[0,1,1],[1,0,0],[0,1,0]] % n, n-1)
perrin2(n) := dot(qpowmod2(n)(2), [2,0,3]) == 0
perrin2(9876543211) ==> true
Update: it seems the limit is not really due to matrix power, but the modulo.
Example: Perrin Primality test
qpowmod(n) := ([[0,1,1],[1,0,0],[0,1,0]] % n) ^ (n-1)
perrin(n) := dot(qpowmod(n)(2), [2,0,3]) == 0
map(range(2, 10), x -> x * perrin(x)) ==> [2, 3, 0, 5, 0, 7, 0, 0]
However, the code will not work for n > 2^31
perrin(9876543211) ==> "Abs Error: Bad Argument Type"
To fix it, need another matpow version that can handle bigger n:
matpow2hlp(a, n, half) := ifte(odd(n), a*half, half) * half
matpow2(a, n) := ifte(n<2^31, a^n, matpow2hlp(a, n, matpow2(a, n div 2)))
qpowmod2(n) := matpow2([[0,1,1],[1,0,0],[0,1,0]] % n, n-1)
perrin2(n) := dot(qpowmod2(n)(2), [2,0,3]) == 0
perrin2(9876543211) ==> true
Update: it seems the limit is not really due to matrix power, but the modulo.