Dichotomie
| Calcul de an = |
| (an/2)2 |
si n est pair |
| a(an/2)2 |
si n est impair |
|
let rec pow = function a -> function n ->
if ((n mod 2) = 0)
then
if (n = 0)
then 1
else
let res = pow a (n / 2) in res * res
else
if (n = 1)
then a
else
let res = pow a (n / 2) in a * res * res ;;
On peut généraliser 0, 1 et * :
let rec dich = fun zero un op a n ->
if ((n mod 2) = 0) then
if (n = 0)
then zero
else
let res = dich zero un op a (n/2) in
op res res
else
if (n = 1)
then un
else
let res = dich zero un op a (n/2) in
op a (op res res) ;;