Mostra notizie nelle discussioni
Avatar
Scritto da
Non Autenticato
il 2009-04-08 20:32:00.0 alle 2009-04-08 20:32:00.0
expmod: come renderlo iterativo?
Ho questo codice che esegue in modo efficiente l'operazione base**exp % m

(defun expmod (base exp m)
  (cond ((zerop exp) 1)
        ((evenp exp)
          (rem  (square (expmod base (/ exp 2) m)) m))
        (t
          (rem  (* base (expmod base (1- exp) m)) m))))


che in python sarebbe

def expmod (base, exp, m):
  if exp == 0:
    return 1
  elif exp%2==0:
    return (expmod(base,exp/2,m)**2)%m
  else:
    return (expmod(base,exp-1,m)*base)%m


non riesco a renderlo iterativo A bocca storta In lisp non mi interessa ma in Python guadagnerei in efficienza...

Pagina generata in 6 millisecondi

Utenti attivi: 30 nell'ultimo minuto, 95 negli ultimi cinque minuti, 145 negli ultimi 15 minuti