Chapter 5: Integer Sequences and Their Application in Learning
To be a programmer in any language, a person needs more than information. There must be a motivation for something you want to make. The challenge is that when you are a beginner, it can be easy to get discouraged because you won’t be making anything big or impressive to other people at the start. All you have to work with in most programming languages is displaying text and numbers.
Later on, you can learn to use third-party libraries or native APIs for your operating system. However, what I have always disliked is that the internals of how they work are hidden or obfuscated so that you don’t know how they work.
But if you love math as I do, you will never have a problem testing your ability by writing small programs to print integer sequences. In this chapter, I will be sharing 3 of my favorite sequences.
If you have the ebook edition of this book, you will be able to click the links above and learn more about these sequences. Either way, I will show you the code that makes printing these sequences easy. even in Assembly Language
Fibonacci numbers
1 org 100h
2 main:
3
4 mov word [radix],10
5 mov word [int_width],1
6
7 mov ax,0
8 mov bx,1
9
10 Fibonacci:
11
12 call putint
13 add ax,bx
14 push ax
15 mov ax,bx
16 pop bx
17 cmp ax,1000
18 jb Fibonacci
19
20 mov ax,4C00h
21 int 21h
22
23 include 'chastelib16.asm'
When executed, that program will output the following sequence
1 0
2 1
3 1
4 2
5 3
6 5
7 8
8 13
9 21
10 34
11 55
12 89
13 144
14 233
15 377
16 610
17 987
Just by looking at it, hopefully you see the pattern. Each number is the sum of the previous two numbers. The loop in this program needed to swap the numbers in ax and bx each time before the next add. Technically, there are two other ways I could have achieved it. I could have used ecx as a temporary storage. I also could have used the xchg instruction, which does the same thing, but the stack provided me a convenient way of doing it. We only needed to save the ax register before it was overwritten with bx, then we popped into bx the pushed ax from earlier. None of these methods is more correct than any other, but I tend to favor simplicity and therefore am limiting the type of instructions I use. I also think that using a third register or even another memory location is acceptable for something like this. Still, since the stack is already used for function calls and is an expected part of Assembly, there is no reason not to use it, especially when we only need to save one register.
Powers of 2
1 org 100h
2 main:
3
4 mov word [radix],10
5 mov word [int_width],1
6 mov [int_newline],0
7
8 mov cx,0
9
10 mov [array],byte 1
11
12 powers_of_two:
13
14 ;this section prints the digits
15 mov bx,[length]
16 array_print:
17 dec bx
18 mov ax,0
19 mov al,[array+bx]
20 call putint
21 cmp bx,0
22 jnz array_print
23 call putline
24
25 ;this section adds the digits
26 mov dl,0
27 mov bx,0
28 array_add:
29 mov ax,0
30 mov al,[array+bx]
31 add al,al
32 add al,dl
33 mov dl,0
34 cmp al,10
35 jb less_than_ten
36
37 sub al,10
38 mov dl,1
39
40 less_than_ten:
41 mov [array+bx],al
42 inc bx
43 cmp bx,[length]
44 jnz array_add
45
46 cmp dl,0
47 jz carry_is_zero
48
49 mov [array+bx],1
50 inc [length]
51
52 carry_is_zero:
53
54 ;keeps track of how many times the loop has run
55 add cx,1
56 cmp cx,64
57 jna powers_of_two
58
59 mov ax,4C00h
60 int 21h
61
62 length dw 1
63 array db 32 dup 0
64
65 include 'chastelib16.asm'
The above program will display the powers of two. This sequence is 1,2,4,8,16,32,64,128,256, etc., all the way until 18446744073709551616, which is two to the 64th power. You will notice that this is far beyond 32768, which was as high as the powers of two program from chapter 3 was. Normally, we could never achieve this in 16-bit DOS mode if we were dealing with native 16-bit integers. Fortunately, there is a method called Arbitrary Precision Arithmetic.
As fancy as that sounds, it is really just using an array of bytes as if they were decimal digits. These lines define variables for the array and the length of the array.
1 length dw 1
2 array db 32 dup 0
The “length” starts at 1, and the total size of the array is 32 bytes, initialized to zero. These variables form the boundaries of several different loops in the program. This loop is what displays the current used parts of the array.
1 ;this section prints the digits
2 mov bx,[length]
3 array_print:
4 dec bx
5 mov ax,0
6 mov al,[array+bx]
7 call putint
8 cmp bx,0
9 jnz array_print
10 call putline
The bx register is set to the current value of length, which will be 1 at the start of the program. Then, bx is decremented so that it is 1 less than the length. Remember, arrays range from 0 to the length minus 1 in Assembly, just like would be the case in C and other languages.
During this loop, while bx is not 0, we set ax to 0 and then load al (the lower half of ax), with the byte at the address of the array plus the number in the bx register. We call the putint function on this value to print the number in al.
The newline is not printed during this loop because of the following line near the beginning.
1 mov [int_newline],0
By turning the newlines off that putint would normally print, we gain control of exactly when we want to. I created another small function named “putline” which prints a newline when I call it. Here is the source code of the putline function.
1 line db 0Dh,0Ah,0
2
3 putline:
4 push ax
5 mov ax,line
6 call putstring
7 pop ax
8 ret
After the currently used digits in the array are printed, another loop begins that adds the digits to themselves. Each one is loaded into al, then al is added to itself. The ld register, which is initialized to 0, is the “carry” variable. If the result of al+al is less than 10, we jump to the “less_than_ten:” label and write the new digit back to the array in that index. If, however, the digit in al is 10 or above, we have to subtract 10 and then set dl (our carry) to 1 so that the next digit we add to itself will also have the carry added to it.
1 ;this section adds the digits
2 mov dl,0
3 mov bx,0
4 array_add:
5 mov ax,0
6 mov al,[array+bx]
7 add al,al
8 add al,dl
9 mov dl,0
10 cmp al,10
11 jb less_than_ten
12
13 sub al,10
14 mov dl,1
15
16 less_than_ten:
17 mov [array+bx],al
18 inc bx
19 cmp bx,[length]
20 jnz array_add
The process of this loop is basically the same way we would add the digits of numbers on paper. However, since we are adding the number to itself, the process is greatly simplified.
But perhaps the final piece of this powers of two program that needs a special mention is the part that expands how many digits are displayed by incrementing the length if a carry of 1 still remains. If the final digit processed had a result of 10 or greater, the carry in dl would have been set to 1, but there would not be a digit to add this to.
1 cmp dl,0
2 jz carry_is_zero
3
4 mov [array+bx],1
5 inc [length]
6
7 carry_is_zero:
We set the byte at “array+bx” to 1 and then increment the length variable so that the new digit becomes permanently part of the list of bytes that is displayed and added to itself, plus the carry from each previous digit addition.
The total number of bytes declared for the array in the program was 32 with the statement “array db 32 dup 0”. So the loop would stop working if we went beyond this limit. However, it is reasonable to say that if we wanted to, we could get away with reassembling with 30,000 bytes and display powers of two with that many digits. We would still be far under the limit of the 64 kilobyte memory limit for a “.com” program in DOS.
I hope I haven’t lost you with my explanation of the arbitrary precision Powers of 2 program. The original version was written in my first programming language, QBASIC, and was the first time I had successfully learned how to use arrays.
At 14 years old, I was learning the concepts of arrays and memory addresses for the first time. I remember a very helpful user on the Network54 QBASIC forum explained it over and over again until I understood.
The syntax of the Assembly version of the Powers of 2 algorithm may look strange. Still, it follows all the same steps as the original QBASIC program and the C version, which later became part of “Chastity’s Code Cookbook”.
Prime Numbers
1 org 100h
2 main:
3
4 mov word [radix],10
5 mov word [int_width],1
6 mov [int_newline],0
7
8 ;the only even prime is 2
9 mov ax,2
10 call putint
11 call putspace
12
13 ;fill array with zeros up to length
14 mov bx,0
15 array_zero:
16 mov [array+bx],0
17 inc bx
18 cmp bx,length
19 jb array_zero
20
21 ;start by filtering multiples of first odd prime: 3
22 mov ax,3
23
24 primes:
25
26 ;print this number because it is prime
27 call putint
28 call putspace
29
30 mov bx,ax ;mov ax to bx as our array index variable
31 mov cx,ax ;mov ax to cx
32 add cx,cx ;add cx to itself
33
34 sieve:
35 mov [array+bx],1 ;mark element as multiple of prime
36 add bx,cx ;check only multiples of prime times 2 to exclude even numbers
37 cmp bx,length
38 jb sieve
39
40 ;check odd numbers until we find unused one not marked as multiple of prime
41 mov bx,ax
42 next_odd:
43 add bx,2
44 cmp [array+bx],0
45 jz prime_found
46 cmp bx,length
47 jb next_odd
48 prime_found:
49
50 ;get next prime read to print in ax
51 mov ax,bx
52 cmp ax,length
53 jb primes
54
55 mov ax,4C00h
56 int 21h
57
58 include 'chastelib16.asm'
59
60 length=1000
61 array rb length
The primes program uses a method called the “Sieve of Eratosthenes”. It is an ancient but very fast algorithm to implement in almost any programming language. The program can find all primes less than 1000 in less than a second.
A Sieve is a process of elimination. Imagine you have all the numbers from 0 to 100. A prime number, by definition, has only two factors: itself and 1.
The only even prime number is 2. It is the first prime number because 1 times 2 equals 2. There are only two factors. Since all even numbers like 4,6,8,10,12, etc are multiples of 2. We exclude them from the list of possible primes. The new number, which is not crossed out, is 3. We then cross out all multiples of 3. Then the next number still in the list after 3 is 5. 4 doesn’t exist because we already excluded multiples of 2. 5 is our next prime number after 3 for this reason. We cross out all multiples of 5 like 10,15,20,25, etc. In fact, some of these would have already been excluded because they are multiples of 2.
In summary, the primes program has an array of 1000 bytes. We use each of these bytes as items to keep track of whether they are prime or not. Every item in the array starts as 0 (prime until proven otherwise). We print 2 because it is a known even prime. We then do the same for 3 because it is the first odd prime. Then we mark all indexes which are a multiple of 3 as 1(not prime). We then skip ahead to the next odd index, which is not marked.
The result will be 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61. The list contains all odd numbers after 2, and some of them are excluded because they are multiples of other odd numbers.
9 is not prime because 33 is 9. 21 is not prime because 37 is 21. And so it continues.
This prime algorithm requires a lot of memory, and so finding the first billion primes is not something that can be done in a 64 KB DOS program because of memory limitations. However, this method is fast because it uses only addition and subtraction (excluding the division used in the intstr function of my library). On a modern PC running Linux instead of DOS, it is easier to allocate gigabytes of memory and find lists of even higher primes.
How to use these examples
My suggestion is that you download the examples in this chapter from my github repository rather than trying to type them by hand or copy past them. That way you can assemble them with FASM and run them in the DOSBox emulator to see how they work.
These programs can produce long lists of numbers and so I can’t include all the output in this book. You will have to run them to get the full picture of how magnificent they are!