This lesson covers:
- Variables and the rules for naming variables
- Assignments, to give variables a value
- Entering programs into a text editor and running them in bc
You should read Lesson 1 before this one.
Syntax for assignments
If you want to follow along for this part, open a terminal, like in Lesson 1. Again, start up bc by entering bc -lq at the prompt:
christopher:~$ bc -lq
An assignment is how you give a variable a value. It looks like this:
x = 1729
The variable x gets the value on the right side of the equals sign, in this case 1729. If you assign a new value to x, it forgets that it ever used to be 1729:
x = 2^23 - 7^7 - 48^3 - 52^4
When you enter an assignment, nothing shows up. But you can always see what value a variable has by entering it on a line by itself:
x 142857
And if you use the variable in an expression, it's replaced by its value:
2*x 285714 4*x 571428 7*x 999999
Differences from Algebra
Because of the equals sign, assignments look kind of like equations in algebra, but they're not really the same thing. The left of the equals sign has to be a variable and nothing else:
x + 4 = y (No.)
1+x+x^2+x^3+x^4+x^5+x^6 = (x^7-1)/(x-1) (Just stop.)
Updating variables
There's a shorter way to type x = x + 1, and it's:
x += 1
So if x was equal to 142857 and you entered x += 1, now x is equal to 142858. The two assignments are exactly the same. It also works with the other operations:
- x *= 10 is the same as x = x * 10
- x /= d + 1 is the same as x = x / (d + 1)
- x ^= 7^y + 3 is the same as x = x ^ (7^y + 3)
The shorter versions tend to be a little clearer, so we'll use them when we can.
That's enough to get us started. Let's write our first program. About time, huh?
Fibonacci numbers
The Fibonacci numbers appear all over the place. The original problem, by Leonardo of Pisa in 1202, was about a ridiculously fast-growing rabbit population. At the end of the 1st month, there's 1 rabbit. At the end of the 2nd month, there's also 1 rabbit. Every month after that, the number of rabbits is the last two months added together. You can see, for instance, that after 6 months there will be 8 rabbits:
| 1 | 1 |
|---|---|
| 2 | 1 |
| 3 | 2 = 1 + 1 |
| 4 | 3 = 1 + 2 |
| 5 | 5 = 2 + 3 |
| 6 | 8 = 3 + 5 |
The question is, how many rabbits are there after 12 months? To answer this question, we're going to use a formula to compute the nth Fibonacci number without computing all the numbers before it, called Binet's Formula. The nth Fibonacci number is:
$${φ^n - (1-φ)^n}/{√{5}}$$
where $$φ = {1 + √{5}}/2 = 1.6180339887....$$
The number φ (or phi) is called the Golden Ratio. It's actually a fairly significant number, but it's kind of overrated. Some people think it shows up everywhere in nature and architecture and stuff, but if you look closely it's not as common as they claim.
Hey, don't go telling people that I'm hating on the Golden Ratio, though. I just like to use it where it actually appears. Like Binet's Formula.
Opening a text editor
We need to write a program that uses Binet's Formula to tell us the 12th Fibonacci number. For that we need a text editor, which is just an application where you can enter text and save it to a file. In bc, you never technically need to save your programs to files. Running a program saved to a file is exactly the same as just typing that program into the terminal. But if you make a mistake or want to change your program, it's much easier to update the file in the text editor than it is to enter the whole program over again in the terminal.
A vast array of tools exist to help you write programs. People will tell you that their favorite tool is essential for programming well, but here at Smooth Programming, we prefer using the simplest one available, so a text editor will be fine. Popular text editors include Notepad, TextEdit, gedit, Notepad++, Kwrite, Emacs, and Vim. Any of them is fine.
- How to open Notepad in Windows
- How to use TextEdit as a text editor on Mac OS X
- How to open gedit on Ubuntu
Once you have a text editor open, you can enter your program and save it to a file. When you run that file with bc, the lines of the program will be run exactly as if you'd entered them in the terminal.
Writing and running the first program
I would solve this problem with a 4-line program:
- An assignment to the variable n, showing which Fibonacci number we want.
- An assignment to the variable r (because I can't type φ) for the Golden Ratio.
- A line that displays the solution using Binet's Formula.
- A line that says halt, which exits bc.
n = 12 r = (1 + sqrt(5)) / 2 (r^n - (1 - r)^n) / sqrt(5) halt
I'm calling the file fib.bc, but you can call it whatever you want. Make sure you know what folder you're saving the file in. Once you've saved the file, go back to your terminal. You might need to cd (change directory) to the folder where you saved your program. I saved mine in a folder called smooth, so I start by changing folders:
christopher:~$ cd smooth christopher:~/smooth$
Once you're in the right folder, run the program by entering bc -lq followed by the filename. It might look something like this:
christopher:~/smooth$ bc -lq fib.bc 143.99999999999999999569 christopher:~/smooth$
Fibonacci numbers are always whole numbers, so there's some rounding error here, but clearly it should be 144.
Problem 1: Population Growth
How many months does it take for the rabbit population to reach 1 billion? That is, what's the first Fibonacci number that's greater than 1,000,000,000? You can use the program you wrote to solve this problem. Modify the program so that instead of finding the 12th Fibonacci number, it finds the 50th Fibonacci number, and run it again. Keep modifying the program until you find the smallest n that gives you a 10-digit number.
The answer is 45. Here's what you should get if you run the program with n = 44:
701408732.99999999991538943605
so the 44th Fibonacci number is 701,408,733. And here's what you get with n = 45:
1134903169.99999999985987998604
so the 45th Fibonacci number is 1,134,903,170. Clearly, rabbit populations in real life don't follow the Fibonacci numbers.
And a good thing too. Who wants to wait a whole 45 months to get a billion rabbits? What if I want them right now??
Variable names
All programming languages have different rules for what's a legal variable name. In bc, variables can use lowercase letters, numbers, and underscores, and they have to start with a letter. Variables can be one letter long like in math, such as a, j, or x, or they can be longer like count, number_of_paths, or eight03_d_rp_dm_497_3_c (if you want to be a jerk about it).
Many programming languages have reserved names, which means you can't use them as variable names because they're used by the language itself. In bc there are 23 reserved names. You've already seen sqrt and halt, and we'll cover most of the others in later lessons. You don't need to memorize them. Just remember that if your program isn't doing what you want, maybe you're trying to use a reserved name.
auto break continue define else for |
halt history ibase if last length |
limits obase print quit read return |
scale sqrt warranty while void |
Choosing the right name for a variable takes skill, since you want your names to be detailed but not too detailed. It's a pretty boring topic, which we're just going to skip. When you write large programs, you need to worry more about what your variables are called, but the short programs we write here at Smooth Programming can usually get by with pretty short names.
Heron's Formula
Blah blah blah. Let's solve another problem. What's the area of a 2-3-4 triangle (meaning a triangle whose sides are 2, 3, and 4 units long)? We can get the answer using something called Heron's Formula. Heron of Alexandria was an ancient Greek engineer who invented the vending machine. Before he came along, the world was pretty miserable, because nobody had any clue how big their triangles were:
Area = $$√{s(s-a)(s-b)(s-c)}$$
where $$s = {a+b+c}/2$$
The program should start by assigning three variables for the lengths of the sides. Let's call them a, b, and c. It should end with halt:
a = 2 b = 3 c = 4 halt
In the middle, it should use Heron's Formula to find the area of the triangle and output it. Try to complete the program yourself. If you do it right, it should run and give you this solution:
christopher:~/smooth$ bc -lq heron.bc 2.90473750965556266388
If you can't figure it out, check out one example of the completed program:
a = 2 b = 3 c = 4 s = (a + b + c) / 2 sqrt(s*(s-a)*(s-b)*(s-c)) halt
Make sure you have your program working before trying the next problem.
Problem 2: Comparing triangles
Say you've got four triangles: 6-8-12, 5-9-9, 4-11-11, and 7-7-7. Which one is the largest, and which one is the smallest?
You can solve this problem by changing the values of a, b, and c in your program and running it for each of the four triangles.
Here's the areas of the four triangles, in order from smallest to largest:
| 7-7-7 | 21.2176... |
|---|---|
| 6-8-12 | 21.3307... |
| 5-9-9 | 21.6145... |
| 4-11-11 | 21.6333... |
Next time
We're doing great! In Lesson 3 we'll see how to make our programs a little more polished.
No comments:
Post a Comment