aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
authorGravatar Pierre-Marie Pédrot <pierre-marie.pedrot@inria.fr>2016-09-26 02:30:45 +0200
committerGravatar Pierre-Marie Pédrot <pierre-marie.pedrot@inria.fr>2016-09-26 16:08:48 +0200
commit5d36de8e2304661e76ac433d5dd90c13b3b86c72 (patch)
tree06b361b179fa775e2fa9f3448372a91dc5d99a24
parentad56f07611f78abb612e8c8c22866ea45040f11e (diff)
Fast russian peasant exponentiation in Nsatz.
-rw-r--r--plugins/nsatz/ideal.ml16
1 files changed, 10 insertions, 6 deletions
diff --git a/plugins/nsatz/ideal.ml b/plugins/nsatz/ideal.ml
index 67355ccc3..7c2178222 100644
--- a/plugins/nsatz/ideal.ml
+++ b/plugins/nsatz/ideal.ml
@@ -457,13 +457,17 @@ let puisP p n=
match p with
[] -> []
|_ ->
+ if n = 0 then
let d = nvar (snd (List.hd p)) in
- let rec puisP n =
- match n with
- 0 -> [coef1, Array.make (d+1) 0]
- | 1 -> p
- |_ -> multP p (puisP (n-1))
- in puisP n
+ [coef1, Array.make (d+1) 0]
+ else
+ let rec puisP p n =
+ if n = 1 then p
+ else
+ let q = puisP p (n / 2) in
+ let q = multP q q in
+ if n mod 2 = 0 then q else multP p q
+ in puisP p n
let rec contentP p =
match p with