Hello

Brad Dominy


Digits of π

In celebration of Pi Day, here is an AppleScript I wrote that outputs the digits of π until the machine runs out of memory and crashes horribly.

(*

From the paper "An Unbounded Spigot Algorithm for the Digits of Pi"
http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/spigot.pdf

*)

property MINUS : -1
property PLUS : 1

set q to {1}
set r to {0}
set t to {1}
set k to {1}

repeat

    set n to divide(add(multiply({3}, q), r), t)

if compare(divide(add(multiply({4}, q), r), t), n) = 0 then

    log n
    set q to multiply({1, 0}, q)
    set r to multiply({1, 0}, subtract(r, multiply(n, t)))
else

    set r to add(multiply(q, add(multiply({4}, k), {2})), ¬
                           multiply(r, add(multiply({2}, k), {1})))
    set q to multiply(q, k)
    set t to multiply(t, add(multiply({2}, k), {1}))
    set k to add(k, {1})
end if
end repeat

on divide(a, b)

set c to {}

if (count of a) = 1 then
    if item 1 of a = 0 then
        return {0}
    end if
end if

if (count of b) = 1 then
    if item 1 of b = 0 then
        return c
    else if item 1 of b = 1 then
        return a
    end if
end if
if item 1 of a < 0 then
    set a_signbit to MINUS
else
    set a_signbit to PLUS
end if

if item 1 of b < 0 then
    set b_signbit to MINUS
else
    set b_signbit to PLUS
end if

set item 1 of a to (item 1 of a) * a_signbit
set item 1 of b to (item 1 of b) * b_signbit

set row to {}

repeat with i from 1 to count of a

    set the end of row to item i of a
    set row to trim_zeros(row)
    set n to 0
    repeat while compare(row, b) ≠ PLUS
        set n to n + 1
        set row to subtract(row, b)
    end repeat
    set the end of c to n
end repeat

set item 1 of a to (item 1 of a) * a_signbit
set item 1 of b to (item 1 of b) * b_signbit

set c to trim_zeros(c)

set item 1 of c to (item 1 of c) * a_signbit * b_signbit

return c
end divide

on multiply(a, b)
set c to {0}

if (count of a) = 1 then
    if item 1 of a = 0 then
        return c
    else if item 1 of a = 1 then
        return b
    end if
end if
if (count of b) = 1 then
    if item 1 of b = 0 then
        return c
    else if item 1 of b = 1 then
        return a
    end if
end if

if item 1 of a < 0 then
    set a_signbit to MINUS
else
    set a_signbit to PLUS
end if

if item 1 of b < 0 then
    set b_signbit to MINUS
else
    set b_signbit to PLUS
end if

set item 1 of a to (item 1 of a) * a_signbit
set item 1 of b to (item 1 of b) * b_signbit

copy a to t --fast but uses more memory
set b_count to count of b
repeat with i from b_count to 1 by -1
    repeat (item i of b) times
        set c to add(c, t)
    end repeat
    set t to shift(t, 1)
end repeat

set item 1 of a to (item 1 of a) * a_signbit
set item 1 of b to (item 1 of b) * b_signbit

set item 1 of c to (item 1 of c) * a_signbit * b_signbit
set c to trim_zeros(c)
return c
end multiply

on shift(n, d)
repeat d times
    set the end of n to 0
end repeat
return n
end shift

on subtract(a, b)
set c to {}

if item 1 of a < 0 then
    set a_signbit to MINUS
else
    set a_signbit to PLUS
end if

if item 1 of b < 0 then
    set b_signbit to MINUS
else
    set b_signbit to PLUS
end if

if a_signbit = MINUS or b_signbit = MINUS then

    set item 1 of b to (item 1 of b) * MINUS
    set c to add(a, b)
    set item 1 of b to (item 1 of b) * MINUS

else if compare(a, b) = PLUS then

    set c to subtract(b, a)
    if item 1 of c > 0 then set item 1 of c to (item 1 of c) * MINUS

else
    set borrow to 0
    set v to 0

    set a_count to count of a
    set b_count to count of b

    set i to a_count
    set j to b_count

    repeat while i > 0 and j > 0

        set v to (item i of a) - borrow - (item j of b)
        if item i of a > 0 then set borrow to 0

        if v < 0 then
            set v to v + 10
            set borrow to 1
        end if

        set the beginning of c to v mod 10

        set i to i - 1
        set j to j - 1
    end repeat

    repeat while i > 0

        set v to (item i of a) - borrow
        if item i of a > 0 then set borrow to 0

        if v < 0 then
            set v to v + 10
            set borrow to 1
        end if

        set the beginning of c to v mod 10

        set i to i - 1

    end repeat

end if
return trim_zeros(c)
end subtract

on trim_zeros(a)
set a_count to count of a
set i to 1

repeat while i ≤ a_count
    if item i of a ≠ 0 then exit repeat
    set i to i + 1
end repeat

if i ≤ a_count then
    set a to items i thru -1 of a
else
    set a to {0}
end if
return a
end trim_zeros

on add(a, b)
set c to {}

if item 1 of a < 0 then
    set a_signbit to MINUS
else
    set a_signbit to PLUS
end if

if item 1 of b < 0 then
    set b_signbit to MINUS
else
    set b_signbit to PLUS
end if

if a_signbit ≠ b_signbit then
    if a_signbit = MINUS then
        set item 1 of a to (item 1 of a) * a_signbit
        set c to subtract(b, a)
        set item 1 of a to (item 1 of a) * a_signbit
    else
        set item 1 of b to (item 1 of b) * b_signbit
        set c to subtract(a, b)
        set item 1 of b to (item 1 of b) * b_signbit
    end if
else
    set carry to 0
    set a_count to count of a
    set b_count to count of b

    set i to a_count
    set j to b_count

    set item 1 of a to (item 1 of a) * a_signbit
    set item 1 of b to (item 1 of b) * b_signbit

    repeat while i > 0 and j > 0

        set n to (carry + (item i of a) + (item j of b))
        set the beginning of c to n mod 10
        if n < 10 then
            set carry to 0
        else
            set carry to 1
        end if

        set i to i - 1
        set j to j - 1
    end repeat

    repeat while i > 0

        set n to (carry + (item i of a))
        set the beginning of c to n mod 10
        if n < 10 then
            set carry to 0
        else
            set carry to 1
        end if

        set i to i - 1

    end repeat

    repeat while j > 0

        set n to (carry + (item j of b))
        set the beginning of c to n mod 10
        if n < 10 then
            set carry to 0
        else
            set carry to 1
        end if

        set j to j - 1

    end repeat

    set item 1 of a to (item 1 of a) * a_signbit
    set item 1 of b to (item 1 of b) * b_signbit

    if carry > 0 then set the beginning of c to carry

    set item 1 of c to (item 1 of c) * a_signbit

end if

return c
end add

on compare(a, b)

if item 1 of a < 0 then
    set a_signbit to MINUS
else
    set a_signbit to PLUS
end if

if item 1 of b < 0 then
    set b_signbit to MINUS
else
    set b_signbit to PLUS
end if

if a_signbit = MINUS and b_signbit = PLUS then return PLUS
if a_signbit = PLUS and b_signbit = MINUS then return MINUS

set a_count to count of a
set b_count to count of b
if b_count > a_count then return PLUS * a_signbit
if a_count > b_count then return MINUS * a_signbit

set r to 0
set item 1 of a to (item 1 of a) * a_signbit
set item 1 of b to (item 1 of b) * b_signbit

repeat with i from 1 to a_count
    if item i of a > item i of b then
        set r to MINUS * a_signbit
        exit repeat
    end if
    if item i of b > item i of a then
        set r to PLUS * a_signbit
        exit repeat
    end if
end repeat
set item 1 of a to (item 1 of a) * a_signbit
set item 1 of b to (item 1 of b) * b_signbit

return r
end compare

About me

Brad Dominy

Projects

By Language

By Frameworks