[Home]MoonShadow/Calculator

ec2-34-239-151-124.compute-1.amazonaws.com | ToothyWiki | MoonShadow | RecentChanges | Login | Webcomic

BNF: MoonShadow/Calculator

Unary numbers. Digits are separated by underscores, and numbers end in 'u' (so that zero can be represented in a nonzero number of characters).

To add 1 to x, do <x::=1##x>
Comparison is defined on MoonShadow/GeneratorGenerator

Basic idea: count upwards while performing an action on one input until number counted is equal to the other input

Addition: (defined below) to add x to y, set result to x then count y times while adding 1 to result.

Multiplication: to multiply x by y, set result to u then count y times while adding x to result.

Subtraction: to subtract y from x, set count to x and count upwards until count==y. The number of times you counted is the result. You'll need to ensure y is smaller than x otherwise count will never equal y and you will loop forever. You can do this by working out x-y and y-x simultaneously, terminating on whichever one finishes first and returning the difference or an error depending on which is more useful.

Subtraction and comparison are known to be sufficient for TuringCompleteness (todo: find link. Google for things like "single instruction computer" or "subtract and branch if zero" ought to do it).

Maybe I'll be able to get to sleep now :(



Just playing with this, hitting the refresh button, I got the following result:

1 7 u + 4 u = 2 1 u
2 u - 2 u = Negative 0 u
1 u / 1 u =
(...)

I may be being dense, but I have no idea where the (...) came from.  Other cases where 1u/1u have come up have correctly indicated 1u as the result so I don't know why this one was different. --K

Execution is limited to ~16k iterations, to stop infinite loops killing the server. In order to display a two-digit decimal number, the calculator needs to do trial division by 100. This is painfully inefficient in unary math, and we get to the execution limit pretty darned quick. [Here]'s an example trace containing a calculation with two-digit numbers. - MoonShadow




bnf ::= additiontest subtractiontest divisiontest

additiontest ::= random <stored::=r> <x::=r> convert result + random <x::=r> convert result <x::=stored> <y::=r> = addxy <x::=result> convert result


subtractiontest ::= random <stored::=r> <x::=r> convert result - random <x::=r> convert result <x::=stored> <y::=r> = subxy <x::=result> convert result


divisiontest ::= random <stored::=r> <x::=r> convert result / random <x::=r> convert result <x::=stored> <y::=r> = divxy <x::=result> convert result <divisiontest##remainder::=divisiontest_remainder> <divisiontest##u::=nothing> divisiontest##remainder

divisiontest_remainder ::= rem <x::=remainder> convert result

option ::= debug = 0

random ::= <r::=u> _random
_random ::= <r::=1##r> _random | <r::=1##r> _random | <r::=1##r>

define result to be x + y; trashes i
addxy ::= <result::=x> <i::=u> <_addxy##i##y::=_addxy> <_addxy##y##y::=nothing> _addxy##i##y
_addxy ::= <i::=1##i> <result::=1##result> <_addxy##i##y::=_addxy> <_addxy##y##y::=nothing> _addxy##i##y
nothing ::= ""

define result to be x - y; negative if y > x (define negative to perform a silent assignment to a flag if required).
subxy ::= <result::=u> <temp_x::=x> <temp_y::=y> <_subxy##temp_y##x::=_subxy> <_subxy##temp_y##temp_y::=nothing> <_subxy##temp_x##y::=_subxy##temp_y##x> <_subxy##temp_x##temp_x::=negative> _subxy##temp_x##y
_subxy ::= <result::=1##result> <temp_x::=1##temp_x> <temp_y::=1##temp_y> <_subxy##temp_y##x::=_subxy> <_subxy##temp_y##temp_y::=nothing> <_subxy##temp_x##y::=_subxy##temp_y##x> <_subxy##temp_x##temp_x::=negative> _subxy##temp_x##y

define result to be x / y, remainder to be x % y; evaulates underflow if y > x.
divxy ::= <_divxy_acc::=x> <_divxy_y::=y> <_divxy_count::=u> <_divxy_done::=false> <negative::=_divxy_onnegative> _divxy
_divxy ::= <_divxy_count::=1##_divxy_count> <x::=_divxy_acc> <y::=_divxy_y> subxy _divxy##_divxy_done
_divxy_false ::= <_divxy_acc::=result> _divxy
_divxy_true ::= <negative::=_divxy_fractional> <result::=_divxy_count> <remainder::=_divxy_acc> <_divxy##x##y::=_divxy_diff> <_divxy##y##y::=_divxy_same> _divxy##x##y
_divxy_onnegative ::= <_divxy_done::=true>
_divxy_diff ::= <x::=result> <y::=1_u> subxy <negative::=Negative>
_divxy_same ::= <remainder::=u> <negative::=Negative>
_divxy_fractional ::= <result::=u> <remainder::=u> underflow

define result to be x * y.
mulxy ::= <negative::=_mulxy_onnegative> <_mulxy_done::=false> <_mulxy_acc::=u> <_mulxy_x::=x> <_mulxy_count::=y> <_mulxy##y::=_mulxy> <_mulxy##u::=_mulxy_true> _mulxy##y
_mulxy ::= <x::=_mulxy_acc> <y::=_mulxy_x> addxy <_mulxy_acc::=result> <x::=_mulxy_count> <y::=1_u> subxy <_mulxy_count::=result> _mulxy##_mulxy_done
_mulxy_true ::= <result::=_mulxy_acc> <negative::=Negative>
_mulxy_onnegative ::= <_mulxy_done::=true>
_mulxy_false ::= _mulxy

decimal conversion - displays x converted to decimal
horrendously inefficient, but seems to work. Probably best with spaces off.

convert ::= <_convert_x::=x> <_convert_acc::=x> <_convert_power::=1_u> <_convert_underflow::=false> <underflow::=_convert_onunderflow> <_convert_lastpower::=1_u> <_convert##x::=_convert> <_convert##u::=0> _convert##x
_convert ::= <x::=_convert_acc> <y::=_convert_power> divxy _convert##_convert_underflow
_convert_onunderflow ::= <_convert_underflow::=true>
_convert_true ::= <_convert_power::=_convert_lastpower> <underflow::=_convert_display_underflow> <_convert_acc::=_convert_x> _convert_display
_convert_false ::= <_convert_lastpower::=_convert_power> <x::=_convert_power> <y::=1_1_1_1_1_1_1_1_1_1_u> mulxy <_convert_power::=result> _convert

_convert_display_underflow ::= <remainder::=_convert_acc>
_convert_display ::= <x::=_convert_acc> <y::=_convert_power> divxy digit##result <_convert_acc::=remainder> <x::=_convert_power> <y::=1_1_1_1_1_1_1_1_1_1_u> divxy <_convert_power::=result> <_divxy##result::=_convert_display> <_divxy##u::=_divxy_end> _divxy##result
_divxy_end ::= <underflow::=Underflow>

digit_u ::= 0
digit_1_u ::= 1
digit_1_1_u ::= 2
digit_1_1_1_u ::= 3
digit_1_1_1_1_u ::= 4
digit_1_1_1_1_1_u ::= 5
digit_1_1_1_1_1_1_u ::= 6
digit_1_1_1_1_1_1_1_u ::= 7
digit_1_1_1_1_1_1_1_1_u ::= 8
digit_1_1_1_1_1_1_1_1_1_u ::= 9





CategoryGenerator

ec2-34-239-151-124.compute-1.amazonaws.com | ToothyWiki | MoonShadow | RecentChanges | Login | Webcomic
Edit this page | View other revisions | Recently used referrers
Last edited February 11, 2005 11:45 pm (viewing revision 72, which is the newest) (diff)
Search: