Translation To Assembly...

[JigPu]

Do any of you guys out there know how to program assembly? I have this tiny prime number program that makes primes REALLY fast, but I am constantly looking for ways to speed it up. Assembly is supposed to let you make really fast or really small programs depending on what the programmer wants.

If anyone here could help me with the translation, I'd appreaciate it!
JigPu

[PolyPill]

What kind of cpu is this assembly for? I messed with assembly for my ti calcs back in the day, I could prolly refresh my memory and write one out. I could learn assembly for another cpu, but I don't have the time.

[engjohn]

Send me the source code and I will ask my instructor. He programs in C++ and Assembly...
If I ask really nice he might be able to help...

[maha_x]

I know assembly (somewhat). The guestion is CAN it really speed up yer program? Assembly usually offers U the ability to decide yer self what variables need fast access and what can be cached.

Today most developers prefer C/C++ cause there isnt much to gain from Assembly. Except plenty headache :) trust me.

Yer software can probably fit in the L1 of the CPU and all the variables and code is pretty fast accessible allready.

[JigPu]

Yeah... I totally agree with the headache thing. It's for a standard computer. Here is the source for all you interested.

Written in BASIC

CLS
Print "FastPrime Version 3.1"
Print "E-Mail Me At: Comp_Nerd@Juno.Com"
Print "-----------------------------------"
Print
Input "Starting Number" StartNum##
Input "Ending Number" EndNum##
Print

If StartNum##<3 Then
StartNum##=3
Print " 2 ";
END IF
If (StartNum## MOD 2)=0 Then StartNum##=StartNum##+1
T=Timer
For CurrNum##=StartNum## To EndNum## Step 2
If INT(SQR(CurrNum##))=SQR(CurrNum##) Then Goto NextNum
For TestNum##=3 To INT(SQR(CurrNum##))+1 Step 2
If (CurrNum## MOD TestNum##)=0 Then Goto NextNum
Next TestNum##
Print CurrNum##;
NextNum:
Next CurrNum##
Print Timer-T
End

If any of you want to bother, I have a write to file version too.

[JigPu]

EWWWWW.... It didn't indent! I'll just attach a file...

[Mord-Sith]

Assember has to be writen for a specific cpu "standard computer" doesnt work you have to know the exact processor.

[vimal]

There is a relatively standard set of assembly instructions, x86, that will allow assembly programs to run across a variety of processors (namely anything from pentium 1's to athlons - but not the more exotic procs like Alpha, UltraSparc, PowerPC, and MIPS)

Various generations of processors have extra instructions added, like AMD's 3DNow! and Intel's MMX, SSE, and SSE2. Using instructions in these sets will limit which processors your code can run on.

Windows has a built-in utility called debug.exe (accessible from DOS prompt) Debug has an x86 assembler built in. I haven't used it, and I don't know much about x86 assembly specifically, but I'm sure there are web pages that have x86 ASM tutorials using debug.

[JigPu]

When I said standard computer, I ment the x86 instruction set (I don't got a Alpha or Sparc, and I'm not running it on my game boy's Z-80). It would be nice to have it optimized to a pentium 1 level though. Right now, I have the program compiled to 386 code.

And debug is quite an evil little utility. I have an old assembly language programming book, and for the first few chapers, all you do is program in debug. Horible interface, I have a complete assembly package though (thank goodness!). X2B (can't find exe2bin), Link, MASM. I can get assembly source into a working program, so I'm happy on that part.

JigPu

[Pitspawn]

I wrote a whole graphic library in MASM 5.0 called QUBE. It uses some of the fastest methods I could think up. When I used to program in Turbo Pascal, I needed all the speed i could get. Thats why i turned to assembler. I went through DOS Borland C++ and QUBE didnt quite work as well. I modified it quite a bit and then moved on to DJGGP. The speed difference was so great that I didn't bother writing anymore assembler.

Unfortunately, I really dont know how to program assembler in basic so unless you go over to pascal or c++ then I cant help you.

[JigPu]

I think I can do a translation to Pascal... It's such a simple program, just copy a few variables, change the statements a little... VOILA!

I'll try to translate the program into Pascal for you... It's the only other language I know right now, so I can't do no fancy translations.... Mabey I'll throw out a psudo code version so you can write it for yourselves in your specialized languages....

JigPu

[6502kid]

I also will translate this into Pascal for you.

I have Turbo Pascal 7.0 (DOS !!)

Which is still the fastest and most efficient compiler ever made.

I used to do a lot of assembler stuff, but for almost anything
but device drivers and real low level stuff it just takes too much
time.

I will supply you with an executable that should run on ANY
IBM PC or compatible, and the main procedures source code.

I use a bunch of inline assembler code in my pascal programs
so the exe should be as small and fast as you are likely to
get from anything but assembler.

[6502kid]

The attached file contains the executable and source code
for Fprime.exe/pas

The executable is about 8k. Seems to run fast.
Let me know if it is any quicker that the fastest version you
got running now.

I left out my spiffy assembler funtions since most of them
tweak text fields or do video output stuff....

Rename the pas file to txt to view with notepad if you want.

Here is the Pascal Source code for those of you too lazy too
download and unzip the tiny file.... (-;



Program FasterPrime(input,output); (* FasterPrime Ver. 1.0 - SAA *)
(* E-Mail Nobody357@juno.com *)
(* Scott A. Armitage 2001 *)


uses dos;

const
datesize = 8;

Label
NextNum;

type
datestr = string[datesize];

var StartNum, EndNum, CurrNum, TestNum:real;
stime,etime:datestr;



function Time: DateStr;
var
hr,min,sec,hsec: word;
hrs,mins,secs,hsecs: string[2];

procedure fixsize;
begin
if length(hrs)=1 then hrs:='0'+hrs;
if length(mins)=1 then mins:='0'+mins;
if length(secs)=1 then secs:='0'+secs;
if length(hsecs)=1 then hsecs:='0'+hsecs;
end;

begin
gettime(hr,min,sec,hsec);
str(hr,hrs);
str(min,mins);
str(sec,secs);
str(hsec,hsecs);
fixsize;
time:=hrs+':'+mins+':'+secs+'.'+hsecs;
end; (* function Time *)


begin (*main*)
writeln; StartNum:=0; EndNum:=0;
write(' Starting Number: ');
readln(StartNum);
write(' Ending Number: ');
readln(EndNum);
writeln;

If StartNum<3 then
begin
StartNum:=3;
writeln(' 2 ');
end;

If (StartNum/2)=INT(StartNum/2) then StartNum:=StartNum+1;
stime:=time;

CurrNum:=StartNum;
While CurrNum<=EndNum do
begin
If INT(SQRT(CurrNum))=SQRT(CurrNum) then goto NextNum;
TestNum:=3;
While TestNum<=INT(SQRT(CurrNum))+1 do
begin
If (CurrNum/TestNum)=INT(CurrNum/TestNum) then goto NextNum;
TestNum:=TestNum+2;
end;
Writeln(CurrNum:9:2);
NextNum:
CurrNum:=CurrNum+2; (* Step 2 ... *)
end; (*While CurrNum *)


etime:=time;
writeln;
writeln('Start time: ',stime,' End time: ',etime);
end.



Let me know if this does what you want it to....

[JigPu]

Yup! Does exactly what I want (except file output.... but that's a totaly different thing). The only problem is speed. I've been working on my program for about a year now (off and on... a little here, some more there), and it's much faster. I know I said I would translate it to Pascal, but when I ran my translation, it was about 1/2 as fast, and I can't make it any faster.

Prime Number Program Results
Your Program (all primes 1-1,000,000)
Start: 18:40:11 End: 18:43:50
Total: 3 min 39 sec

My Program (same thing)
Total Time: 31.907 sec

I can't seem to find a way to translate it to Pascal right. It allways runs slower... I'll include my whole Prime Number package for everyone to test out, and comment on.

I still have to look through your source, and I'll try to optimize it as much as possible. Wish me luck!
JigPu

[6502kid]

I thought about adding file output, but if you need it, you can
just use the DOS output redirect do send all the output to a
file, or a printer.

I was trying to get the EXE as small as possible...

Open a dos prompt and type "Fprime >fpout.txt"

You will have to input the start and ending numbers in the dark
since the prompts will get redirected to the file.

When the program finishes, edit the fpout.txt file and delete the
input prompts and the top, and the timing line at the end, and
you will have a list of numbers to import into whatever.

More bells and whistles could be added. I could write a timer
function instead of just displaying the times.

Is there any money in this ? Ha !

[6502kid]

Here is the next version of that prime thingy...
(See attached Fprime3.zip for source and exe file)

I made a few changes and speeded it up some, but
unfortunately,(?), yours is still faster....

I did go ahead and add some prompts for screen and or
disk file output.

If you select Y for the file output prompt, it will write all the
primes to a list, 1 per line, right justified.

The file will be FPOUT.TXT. If it exists, it will be overwritten.

I thought I had a library of some fast math routines for this
compiler, but I cant seem to find it....

If I can get it any faster, I will post an update....

[JigPu]

Just ran the optimized program... MUCH faster! You are only about 10 sec. behind my program by my count. That isn't bad at all considering I can only get Pascal to double my time...... Also, I like the thing where you set a boolean depending on screen or file output. I'll incorperate it into my program and see how much it slowes it down.

You seemed to have translated it pretty well, so I am assuming you know BASIC... For you (if you don't) and everyone else who dosen't know BASIC, I am (finally) putting up some source with very in depth commenting.

Here 'ya go!

CLS
Print "FastPrime Version 3.1"
Print "E-Mail Me At: Comp_Nerd@Juno.Com"
Print "-----------------------------------"
Print
(This is just the standard opening if you haven't allready guessed... the CLS clears the screen)

Input "Starting Number" StartNum##
Input "Ending Number" EndNum##
Print
(This chunk gets the starting and ending numbers to find primes from. The starting number is stored into the StartNum## variable, and the ending in EndNum##.
Also... If you were wondering, the ## at the end of my variable names tells the compiler to use extended percision for the numbers. Extended numbers can hold up to somewhere near +1x10^4096 and -1x10^4096. I use extended because it is the only number set that can take full advantage of the 18 digit limit on numbers written to the screen.)

If StartNum##<3 Then
StartNum##=3
Print " 2 ";
END IF
(This checks to see if you have a starting number less than 3. If you do, the program dosen't calculate primes correctly. It also writes out the only even prime to the screen.)

If (StartNum## MOD 2)=0 Then StartNum##=StartNum##+1
(This statement makes sure that you don't have an even starting number. If you do, it increases it by one to the next odd number)

T=Timer
(tuns on the timer)

For CurrNum##=StartNum## To EndNum## Step 2
(OK. Lets examine the FOR stamement here... Basic BASIC (pun intended!) syntax makes us decare the variable to incease with each step (CurrNum##), then the value it takes on initalily (StartNum##) and then write what it goes to (EndNum##). The "Step 2" says to increment CurrNum## by 2 each time the FOR loop restarts (instead of 1).
This statement is the statement that makes CurrNum## equal to the number that needs to be tested for primeality)

If INT(SQR(CurrNum##))=SQR(CurrNum##) Then Goto NextNum
(This does an inital check to see if it is a perfect square of some number. If it is, then it obviously isn't prime. If it ain't prime it goes to "NextNum:".)

For TestNum##=3 To INT(SQR(CurrNum##))+1 Step 2
(Same kind of statement as before. Only now we're increasing the number to test with each time.)

If (CurrNum## MOD TestNum##)=0 Then Goto NextNum
(This performes a modulo operation. If you don't know, MOD (modulo) retuns the remainder of a divsion problem. If you rember back to the days of when you divided and wouldn't write out the decimal, but instead something like 6 remainder 1, the one would be the modulo of the problem. If the modulo is 0 then it evenly divides, and is thus not prime, so it goes to "NextNum:".)

Next TestNum##
(Go back to the FOR statement controlling the TestNum## variable. Increases by 2... yada yada...)

Print CurrNum##;
(The only way this gets executed is when the FOR loop controlling CurrNum## finishes. If the number isn't prime, it is weeded out by the MOD statement, and never hits this statement.)

NextNum:
(It goes here if the number is determined not to be prime)

Next CurrNum##
(Continue the FOR loop controlling CurrNum##. Basicaly get the next candidate prime.)

Print Timer-T
(T was set to timer earlier, and now is subtracted from the current timer value to get the elapsed time.)

End
(Stop the progam. There ain't no more primes to test.)

[JigPu]

Just updated to version 3.2.... Basically took your idea of the boolean controling output, and put it in. It slowed the program down by only a few tenths of a second. Also added the stats in the file version to both screen and file output. That way you can see stats about the primes even if you have them put on the screen.

I also compiled a "b" version of the program. It runs anywhere from 2 to 3 times faster on my computer. The "b" version may not be accurate though, as I turned off the assignment overflow checking (makes sure you don't assign a variable a value too large. assignment overflow checking DOSEN'T check for overflow from additions, and other math). I've used a file compare program to test my normal version against a true list of primes to 100,000 and since they checked out, I tested the "b" version against the normal one up to 1,000,000. Still check out. It should be accurate up to REALLY high numbers.

I'll attach the file for you all.
JigPu

[6502kid]

I will check out the new version.

I first learned basic on a TI-994a when those were almost
new. (I am feeling old these days....)

Just for fun, I wrote a version of the program that solves the
problem using a recursive procedure. It works, but as
expected it will blow the stack if you put in any kind of large
range.

Perhaps if I get bored enough, I will unzip my ancient version
of Turbo Assembler and see what I can do.

[fireball****aka fireball_87]

hay this could be a relly cool benchmark :)

[JigPu]

Originally posted by fireball****aka fireball_87
hay this could be a relly cool benchmark :)
Well.... You know my times... That's on a 466 Cele....
What are your times, and CPU? I've wondered how fast it runs on systems with fast processors!

JigPu

[sfa ok]

Originally posted by JigPu

Well.... You know my times... That's on a 466 Cele....
What are your times, and CPU? I've wondered how fast it runs on systems with fast processors!

JigPu

15.92997 Seconds
78498 Primes Found
4927.692 Primes/Sec.

On my TBird 900@1000.

[fireball****aka fireball_87]

when starting # is 1 and end is 1,000,000


11.589 Seconds 78498 Primes Found
6773.312 Primes/Sec. 7.85 % Prime

[fireball****aka fireball_87]

if you still want to translate it to assembly, heres a prog that will do it for you. http://www.qbasic.com/files/basm286.zip

[JigPu]

I think I've used BASM before.... Didn't like it.
Do you know of any other compilers? Mabey something to compile to 486 code? I've never seen ANYTHING compile beyond 386.....

JigPu

[6502kid]

On my new system, I get this:

4.613 Seconds 78498 Primes Found
17015.61 Primes/Sec.
7.85 % Prime


This is in a MSDos window with everything running...
Screen output only. Prm32B version.

If I hit Alt enter and go to a full screen, it scores 17.357 secs !

I will fire up to a DOS command prompt only and see if
it goes any faster....

[fireball****aka fireball_87]

me new xp box :D

17004 pps :D

[Superman53142]

Would C++ perhaps be faster? It's late, but tommorrow morning I'll rewrite your BASIC proggie in C++ and tell you how fast it is, OK?

[JigPu]

C++ works for me! I finaly decided to attempt to learn C (but so far haven't had the time to write more than 'Hello World') so that I could speed it up some (and hopefully optimize it more on the way :) ).

Let's see how much faster C++ is than aincient BASIC!
JigPu