빠른 지수 함수 만들기

Question

OCaml에서 더 빠른 버전의 지수 함수를 찾는 데 어려움이 있습니다. 여기에 내가 따르려고 몇 가지 지침입니다

1. 보다는이 함수는 n은 B 두 개의 인수를 수신 expt b n ==> b * (b * (b ...)의 전형적인 순환 지수 버전은 기본적으로 나누기를 받아 입장을 정복.
2. n이 홀수 다음 fastexpt b n => b * (b^(n - 1))

가 여기에 지금까지 작성한 코드의 경우 n은 다음, 심지어 다른 fastexpt b n => (b^(n/2))^2 경우 :

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));; 

내 질문은이 : 작성하는 방법이 있나요 expt 기능을 사용하지 않고이 기능을 사용할 수 있습니까?

Answer 1

당신이

또 다른 것은이 때문이다 (우리는 당신이 이미 expt를 선언 한 것을 고려하는 경우) 계산의 나머지 부분에 대한 일반적인 하나를 사용하여 다음 분할을 사용하는 방법을 처음 정복하고 여기에 일을하는지 n이 홀수 인 경우 b * b^((n-1)/2) * b^((n-1)/2)을 반환 할 수 있습니다. 이는 빠른 지수 계산의 목적입니다.

그냥 재귀로 fastexpt를 정의하고 그것을 모든 방법을 사용할 수 있습니다 어떻게해야하나요 : fastexpt` 대신

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;;