2017-10-15 20 views
0

Je n'arrive pas à trouver une version plus rapide de la fonction d'exposant typique dans OCaml. Voici quelques lignes directrices que je suis en train de suivre:Création d'une fonction d'exposant rapide

  1. plutôt que la version exposant récursive typique de cette fonction expt b n ==> b * (b * (b ...) reçoit deux arguments b et n et prend essentiellement diviser pour régner position.
  2. Si n est pair, alors fastexpt b n => (b^(n/2))^2 autre si n est impair alors fastexpt b n => b * (b^(n - 1))

Voici le code que je l'ai écrit jusqu'à présent:

let fastexpt : int -> int -> int 
= fun b n -> 
    if n = 0 then 1 
    else if ((n mod 2) = 0) then (expt b (n/2)) * (expt b (n/2)) 
    else b * (expt b (n - 1));; 

Ma question est: Est-il possible d'écrire cette fonction sans utiliser la fonction expt?

+2

Utiliser 'fastexpt' à la place? –

+0

Peut-être que je ne comprends pas très bien le langage OCaml, mais si je devais inclure fastexpt alors ne devrais-je pas faire la définition initiale de fastexpt comme "laisser rec"? – Sean

+1

@Sean, à partir de https://stackoverflow.com/help/how-to-ask: ** Postez la question et répondez aux commentaires Une fois que vous postez, posez la question dans votre navigateur, et voyez si quelqu'un commente. Si vous avez manqué un élément d'information évident, soyez prêt à répondre en modifiant votre question pour l'inclure. Si quelqu'un publie une réponse, soyez prêt à l'essayer et à lui faire part de vos commentaires! ** Lorsque vous posez une question, acceptez les réponses et répondez aux commentaires ou aux réponses. Toutes vos questions n'ont pas de réponse acceptée ce qui est étrange. Ne soyez pas impoli, les gens sont là pour vous aider, ne partez pas et ne communiquez pas. – Lhooq

Répondre

1

Ce que vous faites ici est d'utiliser la fracture et la méthode conquérir la première fois, puis en utilisant la normale pour le reste du calcul (si l'on considère que vous déjà déclaré expt)

Une autre chose est que si n est impair, vous pouvez retourner b * b^((n-1)/2) * b^((n-1)/2), c'est le but de l'exponentiation rapide.

Ce que vous devez faire est de simplement définir fastexpt comme récursive et utiliser tout le chemin:

let rec fastexpt : int -> int -> int 
= fun b n -> 
    if n = 0 then 1 
    else 
     let b2 = fastexpt b (n/2) in 
     if n mod 2 = 0 then b2 * b2 
     else b * b2 * b2;; 
+3

Si vous essayez d'avoir une exponentielle rapide, vous pouvez essayer d'éviter 'mod' et les divisions car ce sont des instructions lentes sur le CPU. Au lieu de cela, vous pouvez utiliser des opérations de décalage de bits pour une division entière par une puissance de 2, et utiliser des opérations sur bits pour tester la parité du nombre: si le premier bit est mis à zéro, le nombre est pair. Cependant, il est possible que le compilateur OCaml fasse déjà ces optimisations mais cela vaut la peine d'essayer. –

+0

Oui, merci, je répondais en fait d'un point de vue algorithmique mais votre point mérite d'être noté. ;-) – Lhooq

+1

@AnthonyScemama Le compilateur fait ces optimisations. Si vous voulez de l'optimalité, il peut y avoir de la magie noire pour vous assurer que vos entiers sont maintenus sans boîte pendant le calcul (bien que je ne sois pas sûr que ce soit faisable manuellement). – PatJ