PHP는 웹 개발에서 널리 쓰이지만, 수학적 계산과 알고리즘 구현에도 충분히 활용할 수 있다. 본문에서는 대표적인 수학 알고리즘들을 PHP로 구현하는 방법을 살펴본다.

보나치 수열의 세 가지 접근법

피보나치 수열은 각 항이 앞 두 항의 합으로 정의되는 대표적인 재귀 수열이다. PHP에서는 성능과 메모리 특성에 따라 다양한 방식으로 구현할 수 있다.

재귀적 접근

가장 직관적인 구현이지만, 중복 계산으로 인해 큰 입력값에서 성능이 급격히 저하된다.

function fibRec(int $idx): int
{
    if ($idx < 2) {
        return $idx;
    }
    return fibRec($idx - 1) + fibRec($idx - 2);
}

반복적 접근

변수 두 개를 활용해 중간 결과를 저장하며 반복, O(n) 시간 복잡도로 해결한다.

function fibLoop(int $idx): int
{
    if ($idx < 2) {
        return $idx;
    }
    
    $prev2 = 0;
    $prev1 = 1;
    $current = 0;
    
    for ($i = 2; $i <= $idx; $i++) {
        $current = $prev1 + $prev2;
        $prev2 = $prev1;
        $prev1 = $current;
    }
    
    return $current;
}

Generator를 활용한 메모리 절약

대량의 수열 항을 순회해야 할 때 Generator를 사용하면 메모리를 상수 공간으로 제한할 수 있다.

function fibStream(int $terms): Generator
{
    $left = 0;
    $right = 1;
    
    for ($k = 0; $k < $terms; $k++) {
        yield $left;
        $sum = $left + $right;
        $left = $right;
        $right = $sum;
    }
}

소수 판별과 선형 체(Linear Sieve)

기본 소수 판정법

2부터 √n까지 나누어보는 방식. n < 2일 때를 먼저 처리하는 것이 핵심이다.

function checkPrime(int $candidate): bool
{
    if ($candidate < 2) {
        return false;
    }
    if ($candidate === 2) {
        return true;
    }
    if ($candidate % 2 === 0) {
        return false;
    }
    
    $bound = (int)sqrt($candidate);
    for ($divisor = 3; $divisor <= $bound; $divisor += 2) {
        if ($candidate % $divisor === 0) {
            return false;
        }
    }
    return true;
}

선형 체: 빠른 소수 생성

에라토스테네스의 체를 개선한 선형 체는 각 합성수를 그 최소 소인수로만 한 번씩 제거해 O(n) 시간 복잡도를 달성한다.

function linearSieve(int $max): array
{
    $isComposite = array_fill(0, $max + 1, false);
    $primes = [];
    
    for ($num = 2; $num <= $max; $num++) {
        if (!$isComposite[$num]) {
            $primes[] = $num;
        }
        
        foreach ($primes as $p) {
            if ($num * $p > $max) {
                break;
            }
            $isComposite[$num * $p] = true;
            if ($num % $p === 0) {
                break;
            }
        }
    }
    
    return $primes;
}

활용 수학 알고리즘

팩토리얼과 예외 처리

function computeFactorial(int $n): int
{
    if ($n < 0) {
        throw new InvalidArgumentException("음수에 대해서는 팩토리얼을 정의하지 않는다");
    }
    
    $result = 1;
    for ($m = 2; $m <= $n; $m++) {
        $result *= $m;
    }
    return $result;
}

유클리드 호제법

function euclideanGcd(int $x, int $y): int
{
    while ($y !== 0) {
        $remainder = $x % $y;
        $x = $y;
        $y = $remainder;
    }
    return abs($x);
}

팰린드롬 수 판별

function isPalindromeNumber(int $value): bool
{
    if ($value < 0) {
        return false;
    }
    
    $original = $value;
    $reversed = 0;
    
    while ($value > 0) {
        $reversed = $reversed * 10 + ($value % 10);
        $value = (int)($value / 10);
    }
    
    return $original === $reversed;
}

실전 적용 예시

Generator 기반 피보나치를 실제 코드에서 활용하는 모습:

$sequence = fibStream(50);

foreach ($sequence as $index => $fibValue) {
    printf("F(%d) = %d\n", $index, $fibValue);
}

선형 체를 이용한 대량 소수 필터링:

$allPrimes = linearSieve(1000000);
$twinPrimes = [];

for ($i = 0; $i < count($allPrimes) - 1; $i++) {
    if ($allPrimes[$i + 1] - $allPrimes[$i] === 2) {
        $twinPrimes[] = [$allPrimes[$i], $allPrimes[$i + 1]];
    }
}

printf("100만 이하 쌍둥이 소수 쌍의 개수: %d\n", count($twinPrimes));