diff options
| author |  Pierre-Marie Pédrot <pierre-marie.pedrot@inria.fr> | 2016-09-26 02:30:45 +0200 |
|---|---|---|
| committer | Pierre-Marie Pédrot <pierre-marie.pedrot@inria.fr> | 2016-09-26 16:08:48 +0200 |
| commit | 5d36de8e2304661e76ac433d5dd90c13b3b86c72 (patch) | |
| tree | 06b361b179fa775e2fa9f3448372a91dc5d99a24 | |
| parent | ad56f07611f78abb612e8c8c22866ea45040f11e (diff) | |
Fast russian peasant exponentiation in Nsatz.
| -rw-r--r-- | plugins/nsatz/ideal.ml | 16 |
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 |