バッチファイルでProject Euler(42)

Problem 16


べき乗を求める計算なので、バイナリ法を使いましょう。それには多倍長整数の乗算が必要です。4桁ごとに区切って計算すれば比較的やさしいでしょう。乗算するたびに10000で割って次の4桁に加算しています。バイナリ法は再帰を使っていますが、配列を使った計算は配列と言いつつ実際には新しい変数を作っているだけなのでsetlocalが使えません。
そこで:pow_longの結果を受ける変数名を少しずつ変えています。

@echo off

setlocal enabledelayedexpansion
set /a N = 1000
set /a a.size = 1
set /a a_0 = 2
call :pow_long a %N% b
call :sum_digits b
echo %ERRORLEVEL%
exit /b 0

// rem %1 ** %2 -> %3
:pow_long
    if %2 == 0 (
        set /a %3.size = 1
        set /a %3_0 = 1
        exit /b 0
    )
    
    set /a half_e = %2 / 2
    call :pow_long %1 %half_e% %3_
    call :mul_long %3_ %3_ _a
    set /a _r = %2 %% 2
    if %_r% == 1 (
        call :mul_long %1 _a %3
    ) else (
        call :copy_long _a %3
    )
    exit /b 0

// rem %1 * %2 -> %3
:mul_long
    set /a max_index1 = "%1.size" - 1
    set /a max_index2 = "%2.size" - 1
    set /a max_index3 = "%1.size" + "%2.size" - 1
    for /L %%i in (0, 1, %max_index3%) do set /a %3_%%i = 0
    for /L %%i in (0, 1, %max_index1%) do (
        for /L %%j in (0, 1, %max_index2%) do (
            set /a _k = %%i + %%j
            set /a _k1 = !_k! + 1
            set /a n = "%3_!_k!" + "%1_%%i" * "%2_%%j"
            set /a %3_!_k! = !n! %% 10000
            set /a %3_!_k1! += !n! / 10000
        )
    )
    set /a _n = "%3_%max_index3%"
    if %_n% GTR 0 (
        set /a %3.size = %max_index3% + 1
    ) else (
        set /a %3.size = %max_index3%
    )
    exit /b 0

// rem %1 -> %2
:copy_long
    set /a max_index = "%1.size" - 1
    for /L %%i in (0, 1, %max_index%) do (
        set /a %2_%%i = "%1_%%i"
    )
    set /a %2.size = %max_index% + 1
    exit /b 0

:sum_digits
    setlocal
    set /a s = 0
    set /a max_index = "%1.size" - 1
    for /L %%i in (0, 1, %max_index%) do (
        set /a e = "%1_%%i"
        call :sum_digits_rec !e!
        set /a s += !ERRORLEVEL!
    )
    exit /b %s%

:sum_digits_rec
    setlocal
    if "%1" == "" exit /b 0
    set s=%1
    call :sum_digits_rec %s:~1%
    set /a sum = %s:~0,1% + %ERRORLEVEL%
    exit /b %sum%

:print_long
    setlocal
    set s=
    set /a max_index = "%1.size" - 1
    for /L %%i in (0, 1, %max_index%) do (
        if %%i LSS %max_index% (
            set /a e = "%1_%%i" + 10000
            set s=!e:~1!!s!
        ) else (
            set /a e = "%1_%%i"
            set s=!e!!s!
        )
    )
    echo %s%
    exit /b 0