[fricas-devel] [PATCH] inline optimize 'powmod'

[oldk1331]

This patch can speed up function call 'primes(1, 10^7);'
by 20%.

diff --git a/src/algebra/integer.spad b/src/algebra/integer.spad
index a5689694..924ba6db 100644
--- a/src/algebra/integer.spad
+++ b/src/algebra/integer.spad
@@ -183,6 +183,18 @@
-- TT := InnerModularGcd(%, ZP, 67108859 pretend %, myNextPrime)
-- gcdPolynomial(p, q) == modularGcd(p, q)$TT

+ -- copied from IntegerNumberSystem to get inline optimization,
+ -- speeds up functions like 'primes'
+ powmod(x, n, p) ==
+ if negative? x then x := positiveRemainder(x, p)
+ zero? x => 0
+ zero? n => 1
+ y : % := 1
+ z := x
+ repeat
+ if odd? n then y := mulmod(y, z, p)
+ zero?(n := shift(n, -1)) => return y
+ z := mulmod(z, z, p)

)abbrev domain NNI NonNegativeInteger
++ Author:

[Waldek Hebisch]

Post by oldk1331
This patch can speed up function call 'primes(1, 10^7);'
by 20%.

OK.

Post by oldk1331
diff --git a/src/algebra/integer.spad b/src/algebra/integer.spad
index a5689694..924ba6db 100644
--- a/src/algebra/integer.spad
+++ b/src/algebra/integer.spad
@@ -183,6 +183,18 @@
-- TT := InnerModularGcd(%, ZP, 67108859 pretend %, myNextPrime)
-- gcdPolynomial(p, q) == modularGcd(p, q)$TT
+ -- copied from IntegerNumberSystem to get inline optimization,
+ -- speeds up functions like 'primes'
+ powmod(x, n, p) ==
+ if negative? x then x := positiveRemainder(x, p)
+ zero? x => 0
+ zero? n => 1
+ y : % := 1
+ z := x
+ repeat
+ if odd? n then y := mulmod(y, z, p)
+ zero?(n := shift(n, -1)) => return y
+ z := mulmod(z, z, p)
)abbrev domain NNI NonNegativeInteger
--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.