A Calculator
So simple, yet, so powerful. Calculators have been around
for a long time, and Bing provides one of the best Calculators out there on the
web better than Google’s: http://www.bing.com/search?q=42*35
Now, let’s suppose that you want to validate the code
behind a calculator. What you really want are two things:
1) A generator of well-formed mathematical expressions
2) An evaluator (an oracle) of mathematical expressions
The first is needed to generate a vast battery of test
cases. The second is needed to compare the results against what the calculator
is giving you (fight fire with fire!). This post is focusing on the former. The
latter can be accomplished thru a variety of different means:
a) Use another well-known engine as the oracle, such as
WolframAlfa (cool)
b) Use off-the-shelf tools to evaluate mathematical
expressions (cooler)
c) Write your own! (coolest!)
The idea to generate a valid math expression is easily
understood if you think recursively: a valid math expression, in a recursive
and more verbose way, is:
Expression =
A number, OR
A set of operations applied to an Expression
The code follows the principles above, but with
everything in life, there are some caveats, gotchas, tricks and magic that
should be talked into more details:
1. A
number is not always a “number” per say. It can be things like “PI” or “E”.
Take that into account
2. Use
random methods (take a look at my previous post, MyRandom) to jump from
operations to operations
3. Eventually
you may need to give extra weight in your random methods to “incentivize” the
appearance of certain operations over others. For example, usually when you see
mathematical expressions in the wild, there is an overwhelmingly higher
occurrence of simple operators such as {+, -, *, /} compared to more
sophisticated ones such as {sin, cosine, arc-cosine, etc.}. You need to take
that into consideration if you want to produce somewhat natural math
expressions.
4. Parenthesis
do occur in nature. If you consider parenthesis as operations, then there is no need to adjust the grammar
aforementioned. If you however are a more purist mathematician, we should
update the already-loosely-defined grammar above to something like this:
Expression =
A number, OR
A set of operations applied to an Expression, OR
(Expression)
5. Remember
to give the same priority to left-appended expressions as well as to
right-appended ones, otherwise you’ll still be creating valid expressions but
with a perceivable pattern, which you don’t want to, the expressions must have
a sufficiently random appearance
6. Then
we have factorial added to the mix. To recap, N! = 1*2*3*…*N-1*N, with 0! = 1, and with (negative
number)! equals to… well I don’t know, but I’ll assume that factorials can be
applied to positive integers only. And that’s where the problem lies: you can’t
apply factorials to non-integers. Because that fact only, we can’t just treat
factorial as any other operator, nor can we modify the grammar in the following
way:
Expression =
A number, OR
A set of operations applied to an Expression, OR
(Expression) OR
Expression! //Wrong!
If we do as above we’ll eventually end up with something
that is potentially wrong (syntactically and semantically wrong), such as
1.42!. Also, you don’t want to end up with gigantic factorials either, like
(2^64)!. To mitigate these problems we’ll make a small tweak to the grammar
whereas we’ll allow an expression to also be a factorial of a small number:
Expression =
A number, OR
A factorial of a small positive integer,
OR //Right!
A set of operations applied to an Expression, OR
(Expression) OR
There! That way eventually we’ll be producing a
reasonable factorial that can be added to our final expression, something
simple like 4+6!.
7. Last
but not least… we have “i", also known as square root of minus one, or
sqrt(-1). Some brief history: once upon a time there was this man named
Cardano. Arguably a mediocre mathematician and astute, greedy thief, he stole
the solution to the cubic equations from an arguably brilliant and naïve,
unlucky mathematician named Tartaglia, and hence became famous and rich whereas
Tartaglia was forgotten in history, well, not completely, at least he got into
my blog. But Cardano did at least one thing right: one afternoon he was trying
to solve this equation:
X2 – 10X + 40 = 0
The solution requires two numbers a and b such that:
a + b = 10
a * b = 40
Which, he failed to find. He then realized that two funny
numbers would solve this equation:
a = 5 + SQRT(-15)
b = 5 + SQRT(-15)
But of course, SQRT(-15) does not exist. Well, he was
already rich, had nothing to lose and was already used to cheating, so he did
it once again and said: “look, let’s ‘imagine’ that there is such a number
SQRT(-1). I’m going to call it as ‘i’ for imaginary. Now I can solve the
equation (?!)”. And thus, the imaginary numbers were born (from the book “A
Strange Wilderness”, by Amir D. Aczel, page 81). Back to 7:
7. Finally…
we have “i", also known as square root of minus one, or sqrt(-1). You can
still add that number to your generator, but be careful: you want your
generator to generate valid math expressions that can be evaluated by a
somewhat simple evaluator, and whose result should be a number (now I really
mean it). If you generate an equation such as i^3 + 4, such an expression does
not evaluate to a real (real) number. What you want to do then is the
following: whenever you contemplate generating an “i" in your math
expression, do so but raise it to an even number. That way you’ll guarantee that your
expression will always evaluate to a real number. Hence, prefer i^4 + 4, in
which case such expression results in (-1)^2 + 4 = 1 + 4 = 5.
Code follows the above principles and gotchas:
Call ExpressionGenerationInternal(“”, 0, 10), for
example.
public static string
ExpressionGenerationInternal(string
currentExpression, int numberOfItems, int maxNumberOfItems)
{
if
(!String.IsNullOrEmpty(currentExpression)
&& numberOfItems >= maxNumberOfItems)
{
return
currentExpression;
}
else
if (String.IsNullOrEmpty(currentExpression))
{
int
tempCoin = UtilMath.MyRandom(0, 2);
string
tempExpression = (UtilMath.MyRandom(0, 2) ==
0) ? UtilMath.MyRandom(0, 100).ToString() :
(UtilMath.MyRandom(0, 15).ToString() + "!");
return
ExpressionGenerationInternal(tempExpression, numberOfItems + 1,
maxNumberOfItems);
}
int
coin = (UtilMath.MyRandom(0, 100) < 90) ?
UtilMath.MyRandom(0, 5) : UtilMath.MyRandom(0, 20);
string
retVal = "";
switch
(coin)
{
case
0:
if
(UtilMath.MyRandom(0, 2) == 0)
{
retVal =
currentExpression + "+" + UtilMath.MyRandom(0, 100).ToString();
}
else
{
retVal = UtilMath.MyRandom(0,
100).ToString() + "+" +
currentExpression;
}
return
ExpressionGenerationInternal(retVal, numberOfItems + 1, maxNumberOfItems);
case
1:
if
(UtilMath.MyRandom(0, 2) == 0)
{
retVal =
currentExpression + "-" + UtilMath.MyRandom(0, 100).ToString();
}
else
{
retVal = UtilMath.MyRandom(0, 100).ToString() + "-" + currentExpression;
}
return
ExpressionGenerationInternal(retVal, numberOfItems + 1, maxNumberOfItems);
case
2:
if
(UtilMath.MyRandom(0, 2) == 0)
{
retVal =
currentExpression + "*" + UtilMath.MyRandom(0, 100).ToString();
}
else
{
retVal = UtilMath.MyRandom(0, 100).ToString() + "*" + currentExpression;
}
return
ExpressionGenerationInternal(retVal, numberOfItems + 1, maxNumberOfItems);
case
3:
if
(UtilMath.MyRandom(0, 2) == 0)
{
retVal =
currentExpression + "/" + UtilMath.MyRandom(0, 100).ToString();
}
else
{
retVal = UtilMath.MyRandom(0, 100).ToString() + "/" + currentExpression;
}
return
ExpressionGenerationInternal(retVal, numberOfItems + 1, maxNumberOfItems);
case
4:
if
(UtilMath.MyRandom(0, 2) == 0)
{
retVal = currentExpression
+ "^" + UtilMath.MyRandom(0,
100).ToString();
}
else
{
retVal = UtilMath.MyRandom(0, 100).ToString() + "^" + currentExpression;
}
return
ExpressionGenerationInternal(retVal, numberOfItems + 1, maxNumberOfItems);
case
5:
return
ExpressionGenerationInternal("(" +
currentExpression + ")", numberOfItems
+ 1, maxNumberOfItems);
case
6:
return
ExpressionGenerationInternal("cos("
+ currentExpression + ")",
numberOfItems + 1, maxNumberOfItems);
case
7:
return
ExpressionGenerationInternal("sin("
+ currentExpression + ")",
numberOfItems + 1, maxNumberOfItems);
case
8:
return
ExpressionGenerationInternal("tan("
+ currentExpression + ")",
numberOfItems + 1, maxNumberOfItems);
case
9:
return
ExpressionGenerationInternal("asin("
+ currentExpression + ")",
numberOfItems + 1, maxNumberOfItems);
case
10:
return
ExpressionGenerationInternal("acos("
+ currentExpression + ")", numberOfItems
+ 1, maxNumberOfItems);
case
11:
return
ExpressionGenerationInternal("atan("
+ currentExpression + ")",
numberOfItems + 1, maxNumberOfItems);
case
12:
return
ExpressionGenerationInternal("log("
+ currentExpression + ")",
numberOfItems + 1, maxNumberOfItems);
case
13:
return
ExpressionGenerationInternal("ln("
+ currentExpression + ")",
numberOfItems + 1, maxNumberOfItems);
case
14:
return
ExpressionGenerationInternal("sqrt("
+ currentExpression + ")",
numberOfItems + 1, maxNumberOfItems);
case
15:
if
(UtilMath.MyRandom(0, 2) == 0)
{
retVal =
currentExpression + "+" + UtilMath.PIorEorISquare();
}
else
{
retVal = UtilMath.PIorEorISquare() + "+" + currentExpression;
}
return
ExpressionGenerationInternal(retVal, numberOfItems + 1, maxNumberOfItems);
case
16:
if
(UtilMath.MyRandom(0, 2) == 0)
{
retVal = currentExpression
+ "-" + UtilMath.PIorEorISquare();
}
else
{
retVal = UtilMath.PIorEorISquare() + "-" + currentExpression;
}
return
ExpressionGenerationInternal(retVal, numberOfItems + 1, maxNumberOfItems);
case
17:
if
(UtilMath.MyRandom(0, 2) == 0)
{
retVal =
currentExpression + "*" + UtilMath.PIorEorISquare();
}
else
{
retVal = UtilMath.PIorEorISquare() + "*" + currentExpression;
}
return
ExpressionGenerationInternal(retVal, numberOfItems + 1, maxNumberOfItems);
case
18:
if
(UtilMath.MyRandom(0, 2) == 0)
{
retVal =
currentExpression + "/" + UtilMath.PIorEorISquare();
}
else
{
retVal = UtilMath.PIorEorISquare() + "/" + currentExpression;
}
return
ExpressionGenerationInternal(retVal, numberOfItems + 1, maxNumberOfItems);
case
19:
if
(UtilMath.MyRandom(0, 2) == 0)
{
retVal =
currentExpression + "^" + UtilMath.PIorEorISquare();
}
else
{
retVal = UtilMath.PIorEorISquare() + "^" + currentExpression;
}
return
ExpressionGenerationInternal(retVal, numberOfItems + 1, maxNumberOfItems);
};
return
"";
}
private
static string
PIorEorISquare()
{
int
coin = UtilMath.MyRandom(0, 3);
switch
(coin)
{
case
0:
return
"PI";
case
1:
return
"E";
case
2:
int
randomEvenNumber = 2 * UtilMath.MyRandom(0,
30);
return
"(i^" +
randomEvenNumber.ToString() + ")";
};
return
"";
}
}
}
Examples of expressions generated by the above code:
EXPRESSION
|
RESULT
|
37/76+25+15/11!+59^93*28
|
1.37E+166
|
68*83/22^8+90-33-10
|
47.0000001
|
22+41*57*2/6*92*64
|
4586774
|
46*72-78^0!/95/40*73^77+80
|
-6.14E+141
|
68+PI-29-63^40/1!*83
|
-7.81E+73
|
8*1^64+2!/12-99^17
|
-8.43E+33
|
70*5-70^67*14+13/27+7^59
|
-5.86E+124
|
47*0*35-7!-34
|
-5074
|
(11!+16)+90*45+29*44*7
|
39929798
|
8-5!*92^70*98
|
-3.43E+141
|
4+78/0!-53*31+60*39+87
|
866
|
20^61+75+98/19*14!+1^3^49
|
2.31E+79
|
50-10+80-87/57+71
|
189.4736842
|
8+88/4!*89*74^77-28+54+55
|
2.78E+146
|
58*52^65+35/4*50^52-50
|
2.01E+113
|
67/6*53+44/92^77^15-39/38
|
590.8070175
|
61+3^15*82+6*85/99-40+47
|
1176610447
|
97^4!-99-45+84*17^73/89
|
6.28E+89
|
22/51*18/4/22^55
|
2.85E-74
|
32^9+6^6-32-67/35+82
|
3.51844E+13
|
97/3*92/33*92+22-(i^30)
|
8316.010101
|
9+(66/81+66-17+45-58)*57
|
2107.444444
|
5*52-11*99^84
|
-4.73E+168
|
80+80+61-5!+93
|
194
|
64*1^56/20-81
|
-77.8
|
Comments
Post a Comment