Category Archives: Mathematics

Pugs’ love: Mathematics

Getting Recursive with Bench Calculator

This fourth article of the mathematical journey through open source, takes you through the recursive functional power of bench calculator.

<< Third Article

Equipped with the fundamentals of programming functions, we are all set to jump into the spiral of recursion. Frankly speaking recursion is not a spiral, as many would like to see it as. It is more to do with the way our brain works. So, let’s look into it as our brain suggests. Any recursion fundamentally has two parts: the recursive relation and the termination condition(s). For mathematics, recursion is basically to do with functions.

Recursive relation

A function when expressed or defined using the function itself, but of lower order, we refer that as a recursive relation. Typical lower order examples would be f(n) expressed in f(n – 1), f(n – 2), … where n is an integer; f(x) expressed in f(x / 2), … where x is a real number. In case of mathematics, a recursive relation is also called a recurrence relation. Here goes some examples:

Factorial: n! = n * (n – 1)! or fact(n) = n * fact(n – 1)
Fibonacci: fib(n) = fib(n – 1) + fib(n – 2)
Exponent: ex = (ex/2)2 or exp(x) = (exp(x/2))^2

Termination Condition

Now, the point is, as we all understand, if we try to expand these, they will continue for ever, unless we decide to stop at some decent condition. For example, n! = n * (n-1)! = n * (n-1) * (n-2)! = n * (n-1) * (n-2) * (n-3)! = … and so on. So, we decide and say that let’s stop it, when we reach 0, as we assume n to be positive. And hence, n! becomes n * (n-1) * (n-2) * … * 2 * 1 * 0!. And then we define 0! to be 1. This is called the termination condition. And, we would notice that, whenever there is a recursive relation, we would need one or more such termination conditions to stop the relation going forever. The number of termination conditions typically depend on the different lower orders, we have in the recursive relation. For example, factorial of n has just one lower order factorial of (n-1); exponent of x has again just one lower order exponent of (x/2); but Fibonacci of n has two lower orders Fibonacci of (n-1) and Fibonacci of (n-2). Hence, factorial and exponent would have one termination condition and Fibonacci would have two termination conditions.

Together in formation

Based on this understanding, the above recursive relations can be written, as follows:

For factorial:
fact(n) = n * fact(n – 1), for n > 0
fact(n) = 1, for n = 0
For Fibonacci:
fib(n) = fib(n – 1) + fib(n – 2), for n > 1
fib(n) = 1, for n = 1
fib(n) = 0, for n = 0
For exponent:
exp(x) = (exp(x/2))^2, for x > 0.001
exp(x) = 1 + x, for x <= 0.001

What is this 0.001 for the exponent? Note that x is a real number and if it is positive, dividing by 2, how ever many times would never reach absolute zero, though it would become smaller and smaller approaching zero. Hence, we would never be able to stop, if we put x > 0. So, we take an approximation, depending on expected accuracy of the result. And for this reason, we cannot put e(x) just equal to 1 for x < 0.001, but need to have some variability based on x, and hence 1 + x. Moreover, as it makes sense to have x take all real values (positive, zero, and negative), the conditions could be further enhanced by replacing x by its absolute value. So, for exponent,

exp(x) = (exp(x/2))^2, for abs(x) > 0.001
exp(x) = 1 + x, for abs(x) <= 0.001

Together in action

Given that we have these mathematical formulations, putting them down into recursive functions of a programming language is a mere mechanical task. Here, it goes – all three in a single file recursion.bc:

define fact(n) {
    if (n <= 0) # < to avoid -ve value cases
        return 1
    return (n * fact(n - 1)) 
}
define fib(n) {
    if (n <= 0) # < to avoid -ve value cases
        return 0
    if (n == 1)
        return 1
    return (fib(n - 1) + fib(n - 2))
}
define abs(x) {
    if (x >= 0)
        return x
    return -x
}
define exp(x) {
    if (abs(x) <= 0.001)
        return (1 + x)
    return (exp(x/2) * exp(x/2))
}

There execution and usage is demonstrated here:

$ bc -ql recursion.bc
fact(0)
1
fact(5)
120
fib(1)
1
fib(2)
1
fib(3)
2
fib(4)
3
fib(5)
5
fib(6)
8
exp(0)
1
exp(1) # Shall be an approximation
2.71695572946643553835
e(1)
2.71828182845904523536
quit # Get out
$

Summing up

With all these, we have pretty much explored all the functionalities of the bench calculator, and if you are a programming geek, you may even do the next level of stuff with these. Next level stuff? Yes, I mean jumping to the next dimension, vectors, etc using arrays of bc. Aha! But isn’t there a way for non-programmers? Yes, there is octave.

Fifth Article >>

   Send article as PDF   

Bench Calculator to Program Mathematics

This third article of the mathematical journey through open source, takes you through the functional power of bench calculator.

<< Second Article

After going through the basic programming on bench calculator, here’s the time to explore its functional power. As mentioned earlier, we can do functions in bench calculator. Unlike C, it has built-in functions, though the standard math functions and the user-defined functions are similar to as in C.

Built-in Functions

Complete list of bc‘s built-in functions is:

  • length(expr) – returns the number of significant digits in expr
  • read() – reads a number from standard input in the base dictated by the ibase variable
  • scale(expr) – returns the number of digits after the decimal point in expr
  • sqrt(expr) – returns the positive square root of expr, given that expr is non-negative

Here’s a sample execution of the above functions:

$ bc -ql
length(000023.450) # Number of significant digits
5
scale(000023.450) # Number of digits after the decimal
3
sqrt(2) # Square root of 2
1.41421356237309504880
sqrt(-1) # Square root of -1 is an error
Runtime error (func=(main), adr=4): Square root of a negative number
ibase=2 # Changing the input base to 2
x=read() # Wait to read the input in binary and then display
1100 # This is the input
x # Display the read value in the default output base 10
12
quit # Get out
$

Is that the complete list of built-in functions? But no talk of the previously used print. The reason is that print is not a function – didn’t you notice the missing () with print. print is actually a statement in bc, like if, for, … and the syntax of print is: print <list>, where <list> is a comma separated list of strings and expressions

If you have not yet got the hang of this word expression, it is a statement of numbers and variables operated with the various operators and functions.

Standard Math Functions

When bc is invoked with -l option, the math library gets loaded along with. And the following 6 math functions, also get available to use:

  • s(x) – returns sine of x, x is radians
  • c(x) – returns cosine of x, x is radians
  • a(x) – returns arctangent (in radians) of x
  • l(x) – returns the natural logarithm (base e) of x
  • e(x) – returns the value of e raised to the power of x
  • j(n, x) – Bessel function of integer order n of x

All these functions operate with the scale dictated by the built-in variable scale. By default, scale is set to 20. Here’s a sample execution:

$ bc -ql
scale # Show the current scale
20
pi=4*a(1) # Calculate pi as tan-1(1) is pi / 4
pi # Show the value approx. to 20 decimals
3.14159265358979323844
s(pi/3) # Calculate sine of 60° - should sqrt(3)/2
.86602540378443864675
sqrt(3)/2 # value for comparison – note the approx. error
.86602540378443864676
c(pi/3) # Calculate sine of 60° - should be 0.5
.50000000000000000001
l(1) # log(1)
0
e(1) # Value of e1 approx. to 20 decimals
2.71828182845904523536
quit # Get out
$

This all sounds too geeky and mathematical – all going over the head. Okay, let’s forget about that and do some simple stuff. Let’s write our own simple functions – yes user-defined functions.

User-defined functions

Here is how we write a user-defined function (to add two numbers) in bc:

$ bc -ql
define add(x, y) {
	return (x + y)
}
add(3, add(4, 5)) # Lets add 3 with the sum of 4 & 5
12
quit # Get out
$

Given that, the factorial code from our previous learnings can be converted into a function as follows (say in functions.bc):

define factorial(n) {
	product = 1
	for (current_num = 1; current_num <= n; current_num += 1)
	{
		product *= current_num
	}
	return product
}

And then, we can use that function as follows:

$ bc -ql functions.bc # Load the functions while invoking bc
factorial(10) # Compute the factorial of 10
3628800
quit # Get out
$

As now, we have factorial, we can even calculate the series of e, i.e. 1 + 1/1! + 1/2! + …, say upto 1/20! for a good enough approximation. Here’s how it would go

$ bc -ql functions.bc # Load the functions while invoking bc
exp=1
for (i = 1; i <= 20; i++)
{
	exp += (1/factorial(i))
}
exp # Display the computed value of e
2.71828182845904523525
e(1) # Compare with the standard math function
2.71828182845904523536
quit # Get out
$

And as in C, if we need a function only to do actions and not return anything, void is the way.

$ bc -ql
define void designer_print(v) {
	print "---{", v, "}---"
}
designer_print(100) # Print 100 with the designs
---{100}---
quit # Get out
$

With all these fundamentals of functions in bc, next we would dive into its recursive functional power.

Fourth Article >>

   Send article as PDF   

Explore the Power of the Bench Calculator

This second article of the mathematical journey through open source, takes you through the basics of bench calculator.

<< First Article

Faced with the limitations of the shell command expr and other shell constructs, here we are all set to explore the powerful command bc. bc stands for bench calculator. It is not just a command or tool but a complete language in itself. And its power lies in its arbitrary precision-ness with not only integers but with real number. Wondering what that means? It just means that its computation is mostly not limited by size of the integer or real number types, unlike in most programming languages. Thus, this is more closer to our day to day dealing of mathematics, keeping away the internal details of computer’s precision blah blah. So, let’s get started with the first usual maths. And then we will move onto more involved one with variables, conditionals, and later on with functions and recursion.

Basic operations

For integer-only math, you may invoke the bench calculator as bc. For a full-fledged real number math, you may invoke it as bc -l. Once invoked, it will print a welcome message and then wait for you to just type your math statements and press Enter to get your answer. For quitting the bench calculator, you need to press Ctrl-D (^D), on an empty line. All the basic arithmetic operations: addition (+), subtraction (-), multiplication (*), quotient (/), remainder (%), power (^), brackets (()) are just there – with the C-like precedence & associativity rules. An example with all of them in use:

$ bc
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
2 + 2 * 3 - 5 + 21 / 4 * 6 # A basic maths statement
33
(2 ^ 2) ^ 3 # Another one with power & bracket
64
^D

Yes, you guessed it right. # starts a one-line comment as in shell, or like // in C++. For a multi-line comment, you may use /* */ as in C/C++. You may want that in case you are writing a complete program in bc. Yes, you can even do that. How? You may put your math statements (each one on a line by itself) in a file, say in prog.bc, as follows:

2 + 2 * 3 - 5 + 21 / 4 * 6 # A basic maths statement
(2 ^ 2) ^ 3 # Another one with power & bracket
quit # This will complete the program and not wait for more input

And then execute – yes I mean execute, you do not need to compile it – as follows:

$ bc prog.bc
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
33
64
$

Aha! You actually got the welcome message from bc and then your results. To avoid the welcome message, you may add -q option to bc, as follows:

$ bc -q prog.bc
33
64
$

You may also try out the difference in the output of the same program with a -l option, i.e. with real numbers. Then, / would be treated as a complete division, not just a quotient provider. Here’s what you would get:

$ bc -ql prog.bc 
34.50000000000000000000
64
$

Programming with bc

As soon as we say programming, the first thing flashing to your mind might be variables. Yes, so they are there. All the variables must start with a small letter alphabet and then may contain numbers or small letter alphabets. Yes, you read it right – only small letter alphabets (a,b,c,…,z). This is because, capital letters (A,B,C,…) are used to represent numbers in other bases greater than 10. Yes, bc have support for various bases from 2 to 16, and two variables associated with them: 1) ibase: defines the base for input; 2) obase: defines the base for output. By default, both are set to 10, as in our day-to-day usual maths. But can be modified, for more fancier base conversions. Here’s a snippet:

$ bc -ql
ibase # Show the current input base
10
obase # Show the current output base
10
obase=16 # Set the output base to 16
108 # Input in base 10; Output should be in base 16
6C
obase=10 # Set the output base back to 10
ibase=16 # Set the input base to 16
11 # Input now in base 16; Output should be in base 10
17
ibase=10 # Set the input base to 16. 10 is 16 in input base 16.
ibase=A # Set the input base to 10.
obase=2 # Set the output base to 2, i.e. binary
x = 2 * 5 - 1 # Set the variable x to 9 (input base 10)
x # Display the value of x (in output base 2)
1001
x * 2 # This should display 18 in base 2, but x is still 9
10010
obase=10
x++ # Post increment: Display the current value of x and then increment it
9
x # Display the incremented value
10
--x # Pre decrement: Decrement x and then display its value
9
^D

From the demo above, you might have already observed that there is nothing like declaring variable type or so – just assign them using = and then use them. Moreover, bc also have basic conditional and loop constructs: if, for, while, break, continue. And along with are the usual C-like relational (<, <=, >, >=, ==, !=), logical (!, ||, &&), and the operation-assignment (-=, +=, *=, /=, %=, ^=) operators. Note of caution: Their precedence and associativity rules may not be as in C. If you do not understand that, forget about it – just make sure to use brackets for whatever you want to operate first. Here goes two simple programs to demonstrate: 1) Computing the sum of the first n numbers (sum.bc); 2) Computing the product of the first n numbers, i.e. factorial of n (factorial.bc)

-------------------------------- file: sum.bc -----------------------------

print "Enter a positive number: "
num = read()
sum = 0
current_num = 1
while (current_num <= num)
{
	sum += current_num
	current_num += 1
}
print "Sum of first ", num, " numbers is: ", sum, "\n"
quit
-------------------------------- file: factorial.bc -----------------------------

print "Enter a positive number: "
num = read()
product = 1
for (current_num = 1; current_num <= num; current_num += 1)
{
	product *= current_num
}
print "Product of first ", num, " numbers is: ", product, "\n"
quit

The above programs can be tried out by issuing shell commands bc -ql sum.bc and bc -ql factorial.bc, respectively. But, what are those two words: print & read, doing there in the code. What else; they are just two built-in functions, displaying the message to the user and taking a number from the user, respectively. Functions? Yes, bc can do functions as well. That’s what would be our next camping. So, right now, just go ahead and try the above programs.

Third Article >>

   Send article as PDF   

Mathematics through the Shell

This article, which is the first part of the mathematical journey through open source, takes you through the basic mathematics through a shell.

Mathematics is something which is knowingly or unknowingly part of every moment of our life, starting from the interpretation of the moment – the time to shopping to advanced engineering calculations and computations. We have learnt mathematics from our childhood by counting. With the age of computers, we have been taught how to do mathematics with them. In this journey of mathematics, we are going to tour through the various open source softwares with their mathematical capabilities. Today, we start with the most preliminary one the shell.

Shell command ‘expr’

expr supports the basic arithmetic operations: Addition (+), Subtraction (-), Multiplication (\*), Quotient (/), Remainder (%) – with the C-like precedence & associativity rules. So, if that’s what you want, you may use it as follows:

$ expr 2 + 3
5
$ expr 34 – 67
-33
$ expr 23 \* 27
621
$ expr 43 / 6
7
$ expr 43 % 6
1
$ expr 2 + 2 \* 3 – 5 + 21 / 4 \* 6
33

Note the spaces between every one of the expr, numbers, and the operator – expr is very space-sensitive. The power of this simple command is its precision-less-ness. What I mean is, try out the following:

$ expr 1024 \* 1024 \* 1024 \* 1024 \* 1024 \* 1024 \* 1024 \* 1024 \* 1024 \* 1024

And you still don’t get an overflow, but 1267650600228229401496703205376, i.e. 2100.

Also, you may use variables. Here’s an example:

$ x=5; y=6; z=`expr $x + $y`
$ echo $z
11

However, it has its own limitation. Basic one being, you do not have the exponentiation operator. Moreover, you can’t change precedences by using brackets. And that’s where you start looking at the other options.

Shell’s arithmetic expansion

With this, we get the all the mathematical C operators, plus the exponentiation using **. We have the bracketing, and variable usage even without the cryptic $. It is achieved by putting the complete expression to be evaluated, between $((…)) – the arithmetic expander. Here’s a set of examples:

$ echo $(((2+3)*4-2**4/5%6))
17
$ x=y=8; echo $((3 << 4 | x | 2 << y))
568

There are some additional interesting ways to assign variables, as well, using let or declare -i.

$ let x=y=8 z='3 << 4 | x | 2 << y' w=z/3
$ echo $w
189
$ declare -i x=y=8 z='3 << 4 | x | 2 << y' w=z/3
$ echo $w
189

Note that the $((…)) has been replaced by single quoting in assigning the value to z. In fact, in most cases – see the assignment of w – it can be actually assigned directly as in C. Though the single quote for z is required to prevent the shell specially interpreting constructs like <<, >>, |, *, etc, and for it not to be space-sensitive. Otherwise, checkout, this example:

$ declare -i x=y=8 z=++x+y
$ echo $z
17

In fact, the variables can be declared as integer once, and then be operated any number of times, as follows:

$ declare -i x y z
$ x=y=8
$ z=++x+y
$ echo $z
17

And, finally here’s two simple ones:

$ echo $((2 ** 100))
0
$ echo $((2.6 + 3))
bash: 2.6 + 3: syntax error: invalid arithmetic operator (error token is ".6 + 3")

Oops!!! how come 2100 is zero, and we are not able to do real number operations. It has its own limitation. It is limited by the C’s long integer math, typically upto 64-bit computations on today’s computers; and by not having support for non-integer math. That’s where we would look out for something more powerful: the bench calculator.

Second Article >>

   Send article as PDF