Matrix power limit
02-27-2019, 03:28 PM (This post was last modified: 02-27-2019 07:28 PM by Albert Chan.)
Post: #1
 Albert Chan Senior Member Posts: 2,109 Joined: Jul 2018
Matrix power limit
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.
02-27-2019, 05:51 PM
Post: #2 Joe Horn Senior Member Posts: 1,903 Joined: Dec 2013
RE: Matrix power limit
HP Prime in CAS view:
[]^(2^8198) --> []
[]^(2^8199) --> undef

<0|ɸ|0>
-Joe-
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)