DouKaku?

(define (gcd-nodiv m n)
  (cond [(= n m) n]
        [(or (= m 1) (= n 1)) 1]
        [(> m n) (gcd-nodiv n (- m n))]
        [else    (gcd-nodiv m (- n m))]))

;;
;; 以下は測定用
;;
;;ループ回数のカウント
(define (gcd-nodiv/cnt m n cnt)
  (cond [(= n m) (values n cnt)]
        [(or (= m 1) (= n 1)) (values 1 cnt)]
        [(> m n) (gcd-nodiv/cnt n (- m n) (+ cnt 1))]
        [else    (gcd-nodiv/cnt m (- n m) (+ cnt 1))]))

;;メモワイズ版fib
(define fib
  (let1 memo (make-hash-table 'eqv?)
    (lambda (n)
      (cond [(<= n 2) 1]
            [(hash-table-get memo n #f)]
            [else (let1 val (+ (fib (- n 1)) (fib (- n 2)))
                    (hash-table-put! memo n val)
                    val)]))))

mygcd = gcd

using System;
using java.math;
static class Program {
    static void Main(string[] args) {
        BigInteger fib1999 = new BigInteger("2611005926183501768338670946829097324475555189114843467397273230483773870037923307730410719313972291638157639230613843870597997481070930648667960025707364078851859017098672504986584144842548768373271309551281830431960537091677315014266625027123872238011234749984205478230617988978500613170516952885123444971471854671812569739975450866912490650853945622130138277040986146312325044424769652148982077548213909414076005501");
        BigInteger fib2000 = new BigInteger("4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125");
        Console.WriteLine("gcd({0}, {1}) = {2}", fib1999, fib2000, fib1999.gcd(fib2000));
    }
}

require "mathn"

class Fib
  def initialize
    @fib_a=[1,1]
  end
  def [](n)
    (@fib_a.size..n).each{|i| @fib_a<<=@fib_a[i-2]+@fib_a[i-1]}  
    @fib_a[n-1]
  end
end

def gcd(n,m)
  c=0
  until(n==m)
    n,m=m,n if n<m
    return [1,c] if m==1
    m1=m
    while(m1<n)
      m1<<=1
      c+=1       
    end
    m1>>=1
    n-=m1
    c+=1
  end
  [n,c]
end

fib=Fib.new
p gcd(fib[2000],fib[1999])

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Sample106 {
    private final Map<Integer, BigInteger> fibMemo_ = new HashMap<Integer, BigInteger>();

    public BigInteger getFibValue(int index) {
        if (index == 1 || index == 2) return BigInteger.ONE;
        BigInteger fib = fibMemo_.get(index);
        if (fib == null) {
            fib = getFibValue(index - 2).add(getFibValue(index - 1));
            fibMemo_.put(index, fib);
        }
        return fib;
    }

    public static void main(String[] args) {
        Sample106 instance = new Sample106();
        BigInteger fib1999 = instance.getFibValue(1999);
        BigInteger fib2000 = instance.getFibValue(2000);
        System.out.println(fib2000.gcd(fib1999));
    }
}

(defun *gcd (x y &optional (acc 1) (count 0))
  (incf count)
  (cond ((= x y)
         (values count (* acc x)))
        ((and (oddp x) (oddp y)) ; odd, odd
         (*gcd (min x y) (ash (abs (- x y)) -1) acc count))
        ((oddp x) ; odd, even
         (*gcd x (ash y -1) acc count))
        ((oddp y) ; even, odd
         (*gcd (ash x -1) y acc count))
        (t ; even, even
         (*gcd (ash x -1) (ash y -1) (ash acc 1) count))))

(defun fib (x)
  (loop with l = '(1 1) for i from 2 to x
    do (push (+ (car l) (cadr l)) l)
    finally (return (car l))))

(format t "~{Called ~D times, result is ~D~}"
        (multiple-value-list (*gcd (fib 2000) (fib 1999))))

GCD[Fibonacci@1999, Fibonacci@2000]

#!/usr/local/bin/perl
use strict;
use warnings;
use bignum;
use Memoize;

no warnings 'recursion';

sub fib{
    my $n = shift;
    return 1 if $n <= 2;
    fib($n-2)+fib($n-1);
}
memoize 'fib';

sub gcd{
    my ($m, $n) = @_;
    return gcd($n, $m) if $m < $n;
    my $r = $m % $n;
    return $n unless $r;
    gcd($n, $r);
}

sub gcd_nodiv{
    my ($m, $n) = @_;
    return gcd($n, $m) if $m < $n;
    $m -= $n while $m > $n;
    return $n unless $m;
    gcd($n, $m);

}

sub gcd_regexp{
    my ($m, $n) = @_;
    return gcd($n, $m) if $m < $n;
    my $sm = 1 x $m;
    my $sn = 1 x $n;
    $sm =~ s/^$sn//g;
    return $n unless $sm;
    gcd($n, length $sm);
}

sub say { local $\="\n"; print @_ };
say gcd_regexp(fib(25), fib(24));
say gcd_nodiv(fib(1999),fib(2000));

| gcdNoDiv gcdNoDivCount fibMemo fib fib1999 fib2000 |
gcdNoDiv := [:pair |
    [(pair sort; first) = pair second or: [pair last = 1]]
        whileFalse: [pair at: 2 incrementBy: pair first negated].
    pair last].

gcdNoDivCount := [:pair |
    | count |
    count := 0.
    [(pair sort; first) = pair second or: [pair last = 1]] whileFalse: [
        count := count + 1.
        pair at: 2 incrementBy: pair first negated].
    count].

fibMemo := Dictionary new.
fib := [:nth |
    fibMemo at: nth ifAbsentPut: [
        nth < 3 ifTrue: [1] ifFalse: [
            (fib copy fixTemps value: nth-1) + (fib copy fixTemps value: nth-2)]]].
fib1999 := fib copy fixTemps value: 1999.
fib2000 := fib copy fixTemps value: 2000.

fib1999 gcd: fib2000.   "=> 1 "  " 組み込みの GCD "
gcdNoDiv value: {fib1999. fib2000}.   "=> 1 "
gcdNoDivCount value: {fib1999. fib2000}.   "=> 1998 "

import Prelude hiding (gcd)

fib 0 = (0,1)
fib n | even n = let (a,b) = fib (n-1)         in (b, a+b)             
      | odd  n = let (a,b) = fib (halve (n-1)) in (b*b+a*a, b*b+2*a*b)       

halve = (`div` 2)

gcd 1 _ = 1 
gcd a b | a == b = a
        | even a = if even b then 2*gcd (halve a) (halve b)           else gcd b (halve a)
        | odd  a = if odd  b then gcd (min a b) (abs (halve (a - b))) else gcd a (halve b)
        

gcd' 1 _ c = (1,c+1)
gcd' a b c | a == b = (a,c+1)
           | even a = if even b then fstapp (2*) (gcd' (halve a) (halve b) (c+1))
                      else gcd' a (halve b) (c+1)
           | odd  a = if odd  b then gcd' (min a b) (abs (halve (a - b))) (c+1)
                      else gcd' a (halve b) (c+1)

fstapp f (x,y) = (f x,y)

import java.math.BigInteger
import java.math.BigInteger.ONE

implicit def int2big(n:int) = new BigInteger(n.toString)
def gcd(m:BigInteger, n:BigInteger):BigInteger = m.compareTo(n) match {
  case 0 => n
  case x if m == ONE || n == ONE => ONE
  case 1 => gcd(n, m.subtract(n))
  case x => gcd(m, n.subtract(m))
}

:: gcd.bat
@echo off
  setlocal
    set n=0

    echo %1%2|findstr /r "[^0-9]" >NUL 2>&1
    if %ERRORLEVEL% equ 0 (echo %~n0 [NUMBER] [NUMBER]) & goto :EOF

    call :gcd %1 %2 n
  endlocal & echo %n%
goto :EOF

:gcd
  setlocal enabledelayedexpansion
    set a=%1
    set b=%2
    set m=0
    set q=0

    if %a% lss %b% (
      set /a a=%b%-%a%
      set /a b-=!a!
      set /a a+=!b!
    )

    :loop_gcd
      call :mod %a% %b% m
      if %m% equ 0 (endlocal & set %3=%b%) & goto :EOF
      :: 剰余を除数の半分未満にして演算効率を向上
      call :div %b% 2 q
      if %q% lss %m% set /a m=%b%-%m%
      set a=%b%
      set b=%m%
    goto loop_gcd
  endlocal
goto :EOF

:mod
  setlocal
    set m=0
    set q=0

    call :div %1 %2 q

    set /a m=%2*%q%
  endlocal & set /a %3=%1-%m%
goto :EOF

:div
  setlocal enabledelayedexpansion
    set i=0
    set m=%1
    set m_=0
    set n=%2
    set n_=0
    set q=0

    if %n% gtr %m% (endlocal & set %3=%q%) & goto :EOF

    call :msb %m% m_
    call :msb %n% n_
    set /a i=%m_%-%n_%

    :loop_div
      if %i% lss 0 (endlocal & set %3=%q%) & goto :EOF
      set /a "q<<=1"
      set /a "m_=%m%>>%i%"
      if %m_% geq %n% (
        set /a "n_=%n%<<%i%"
        set /a m-=!n_!
        set /a q+=1
      )
      set /a i-=1
    goto loop_div
  endlocal
goto :EOF

:: 最上位ビットを取得(most significant bit)
:msb
  setlocal
    set i=%1
    set n=0

    :loop_msb
      set /a "i>>=1"
      set /a n+=1
    if %i% neq 0 goto loop_msb
  endlocal & set %2=%n%
goto :EOF