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:

-- 
You received this message because you are subscribed to the Google Groups 
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.

Reply via email to