A small and (maybe) interesting program

Mirannan

Well-Known Member
Joined
Jan 20, 2013
Messages
1,791
I found this in my files a couple of days ago. It's very small, but all my own work; a program that runs the Sieve of Eratosthenes (sp?) to generate prime numbers without actually doing any calculations. Written in BASIC (yeah, I know...) Anyway, here it is:

'Sieve of Eratosthenes prime number generator without calculations

dim primes(1000)

n=2
for x=4 to 1000 step 2
primes(x)=1
next x

for x=2 to 1000
if primes(x)=0 then
for y=x+x to 1000 step x
primes(y)=1
next y
end if
next x

for x=2 to 1000
if primes(x)=0 then print x;" ";
next x
 
It IS calculating!
I count at least five calculations.

Sorry for being pedantic (but I've written compilers and interpreters ...) :)
My bad. However, the point is that no calculations are involved in testing whether a number is composite during the process.

BTW, I can only see one calculation. Where are the others?
 
Every loop increment is a calculation. The Machine code does an increment or add or subtract (the compiler often rewrites loops with a decrement and a test that looks for a zero flag set.).
Sometimes the loop exit test is a calculation. Without seeing what machine code is produced, it's not possible to say. Traditional BASIC used a compiler to create tokenised intermediate code (without any re-arrangement) which was then interpreted. Later things, VB4, VB5, VB6 etc compile to a byte code very like the way Pascal P-Machine worked, then runs the p-code on a virtual machine. The VB engine, Java Virtual Machine, the .Net used by VB.net and C# (derived from J++) and Android's/Google's Davik are all actually derived from the design of the p-machine used by UCSD Pascal.
Modern optimising compilers may do very unintuitive things (as far as people unused in writing machine code/Assembler and compilers are concerned).

Unless you KNOW how the BASIC is executed, you really have no idea if a particular BASIC program is efficient, other than normal issues of algorithms (i.e. Bubble sort is rubbish compared to C.A.R. Hoare's Quick Sort).
 

Back
Top