Most of the programs used so far doing the benchmark are using the given algorithm. Long time I thought it is necessary to distinguish between the "classic" BASIC V1 version and e.g. the C-V2 version, but due the feedback here I think the distinction between them is not correct.
The BASIC V1 version is a simple and straight forward implementation of a brute force approach. The particular used BASIC version (a MicroSoft variant) does neither know integer variables nor the modulo function. Further the FOR..NEXT boundaries are computed once, so using the square root isn't a big penalty. These constraints lead to the given program. Later BASICs do know integer variables and accordingly the implementation of the algorithm is adapted in order to verify any effects. This is as well true for other languages. Using their capabilities to construct both loops is simply a continuation. This holds true even for things like variable length division within assembler (Chromatix). So far all programs tested the candidate number against all odd numbers up to the point where the quotient becomes smaller than the divisor or the remainder was zero.
The latest discussion was about extending the algorithm to avoid divisions where possible. This is of course something different. The results of these tests cannot be compared in a simple fashion against the "traditional" ones. Of course they can be compared against each other to verify which measure causes which effect. Some may even be counterproductive if the implementation overhead is bigger then the net effect.
In a lazy moment I took the idea of tweaking the algorithm by using a sieve or by wheeling and write some BASIC variants for them. As I use a SYMimlar old NMOS system running at 1 MHz this took some time
and I only run them within 16 bit space but I think one can see some interesting effects. The various source programs are appended. They are quick hacks, neither nice and good readable nor written for utmost performance.
I took the "classic" approach as reference against the "enhanced" versions. -10% means if the reference took 100s the enhanced versions took 90s.
Avoiding divisions by 3 starts great but then the win drops down to 5% only. Avoiding divisions by 3 and 5 are only for small numbers a little better. Sieving (using only primes for division) starts good and maintains its effect perhaps with a little tendency of getting better. Combining sieving and wheeling seems to add linearly.
Next I ported the programs to the Badge where EhBasic V2.22 is installed. Again the "classic" variant is taken for reference:
To my very surprise none of the "enhancements" have had a positive effect! This is a completely different behavior than MS-Basic shows. I am pretty sure that I didn't make a silly mistake. I rerun some of the tests several times without significant changes. Perhaps someone else could verify this strange behavior?
Taking all these numbers into one chart (with corrections for the different clock speeds) shows that EhBasic is still always faster.
Cheers,
Arne
