Basic Speedup Tip

[Mike]

But hmm..

PRINT (SQR(14)*SQR(14))-14 returns 3.7252903E-09
PRINT (SQR(14)*USR(14))-14 returns 3.7252903E-09
PRINT (USR(14)*SQR(14))-14 returns 0
PRINT (USR(14)*USR(14))-14 returns 0

I'm not sure I can explain this behavior.

More interesting, this anomaly doesn't appear, if you assign the results to a variable first:

S=SQR(14):U=USR(14):PRINT U*S-14, S*U-14

Both expressions return 0.

But this isn't restricted to my USR() function. After some tries I came up with:

PRINT 2.345*3.456
8.10432001

PRINT 3.456*2.345
8.10432

the correct result of course being 8.10432 ...

PRINT 2.345*3.456-8.10432
3.7252903E-09

PRINT 3.456*2.345-8.10432
0

A=2.345:B=3.456:PRINT A*B,B*A
8.10432001
8.10432001
(now we have an identical, but still slightly inaccurate answer.)

Seems, as if the VIC's multiplication is not commutative, unless the operands come from memory (as opposed from FAC). The C=64, and C=16, and C=128 show the same behaviour. Which is sad, as even though the associative, and distributive laws usually don't hold with FP arithmetic, at least the commutative law should hold on both addition and multiplication.

Michael

[carlsson]

It got to do with converting decimal strings to FAC in one way or another, but one would assume they convert in the same way always.

[Mike]

Further analysis:

Integer numbers can be represented exactly (as long as they're not greater than 2^32), so we can construct 2.345 and 3.456 as decimal fractions. The division of two exact integers is possibly the best way to get accurate fp numbers:

And there:

PRINT 2.345-2345/1000
9.31322575E-10
PRINT 3.456-3456/1000
0

we see, that 2.345 (opposed to 2345/1000) is presumably represented outside the required accuracy, which is the reason that we get:

A=2.345:B=3.456:PRINT A*B
8.10432001

Still this could be tolerated, but the multiplication in expressions simply is done wrong:

In continued calculations without parenthesis:

- One operand (the "running result") is always fetched from the FAC (which has an extra rounding byte),
- while the other operand is fetched from memory.

And the multiplication of two operands with two different accuracies is not commutative. If we force the running result into, and then out of memory we get a consistent result:

PRINT (2.345*1)*(3.456*1),(3.456*1)*(2.345*1)

or

PRINT (2.345+0)*(3.456+0),(3.456+0)*(2.345+0)

or

A=2.345:B=3.456:PRINT A*B (as above)

will do the trick.

Michael

P.S.: Since we're now clearly off-topic, we should continue further discussion in a new thread, and move the postings since Jun 18 to this new thread (but leaving a copy of the Jun 18 post here).

[GreyGhost]

Another thing to add hear. It was noted earlier that you could gain speed by defining the variables that are used most at the beginning of the program. This can be done easily with the DIM command.

0 DIM A,B,C,D,E,F,G

This line sets the variables to zero. I use A,B and so* on because they are the quickest to be looked up. You can use any Letter or Letter-Number combo you like. Just scan your program and find the variable that is used most(and in a useful spot) in your program and start the DIM statement with that variable. Then find the next most used/useful variable and so on.

Later,

*Would the variable AA come after A or is it B as the quickest to be looked up? Which is faster, AA or C?

[Mike]

Hi Rob!

How quick the variables are found only depends on the order they're defined in the program, not their position in the alphabet.

Still two-letter variables, and letter-digit variables need two characters to match, for that reason they're slightly slower - comparable to as if they'd been declared one place later in the list as single-letter variables.

Greetings,

Michael

[Jeff-20]

I use the same idea, but I always define the variables:

A=0, B=0, C=0, etc.

Because I thought DIMA, B, C uesd more memory. Was my assumption wrong?

[GreyGhost]

I just tried this:

10 DIM A,B,C,D,E,F,G

before RUN = 3562 bytes free = 19 bytes
after RUN = 3513 bytes free = 68 bytes

and:

10 A=0:B=0:C=0: D=0:E=0:F=0:G=0

before RUN = 3549 bytes free = 32 bytes
after RUN = 3500 bytes free = 81 bytes

They both take up the same amount of extra space after running(49 bytes).

Maybe this is more of a memory saver than a speed up.

[Mike]

This is a good place to point out, that no fiddling with variable names, or their order of declaration can rescue an otherwise bad algorithm.

A good example are sorting algorithms. Bubble-Sort, while easily implemented (I can write that routine down straight from memory) is a bad algorithm - such that it really should be forbidden to teach it to those new to programming. I just use it here, to state the point, to compare it with Quick-Sort.

Quick-Sort is more complicated to program. I confess I always have to look it up in a book, when I need to implement it myself. Luckily C has a built-in Quick-Sort.

First comes the example. Replace GOSUB 50 in line 13 with GOSUB 20 to test Bubble-Sort instead of Quick-Sort. N is specified in line 11.

Greetings,

Michael


I use the variant of Quick-Sort, that sorts the smallest sub-array first. This minimizes stack usage. DIMS(31) is enough to sort up to 65535 elements.

Quick-Sort also works with String-Arrays (use A$(), A$, and X$ instead). If you want to sort other arrays alongside A(), place the additional swap operation(s) between lines 55 and 56.

Code: Select all

10 DIMS(31):SP=0:REM ** STACK FOR QUICK-SORT
11 N=10:DIMA(N)
12 FORT=0TON:A(T)=RND(1):NEXT
13 T1=TI:L=0:R=N:GOSUB50:T2=TI
14 FORT=0TON:PRINTA(T):NEXT
15 PRINTT2-T1
16 END
18 :
19 REM ** BUBBLE-SORT
20 IFR<=LTHENRETURN
21 F=0:FORT=LTOR-1:IFA(T)>A(T+1)THENA=A(T):A(T)=A(T+1):A(T+1)=A:F=1
22 NEXT:IFFTHEN21
23 RETURN
29 :
49 REM ** QUICK-SORT
50 IFR<=LTHENRETURN
51 I=L:J=R:X=A((L+R)/2)
52 IFA(I)<XTHENI=I+1:GOTO52
53 IFA(J)>XTHENJ=J-1:GOTO53
54 IFI>JTHEN57
55 A=A(I):A(I)=A(J):A(J)=A
56 I=I+1:J=J-1
57 IFI<=JTHEN52
58 IFJ-L<R-ITHENS(SP)=I:S(SP+1)=R:SP=SP+2:R=J:GOSUB50:GOTO60
59 S(SP)=L:S(SP+1)=J:SP=SP+2:L=I:GOSUB50
60 SP=SP-2:L=S(SP):R=S(SP+1):GOTO50

You'll see, for N up to 10, they're roughly on par, Bubble-Sort may even be faster, but look, what happens for greater N:

These are the run times in clock ticks:

Code: Select all

Quick-Sort

   N  Run 1  Run 2  Run 3  Run 4  Run 5

  10     56     65     60     61     59
  30    230    221    231    211    207
 100    837    881    867    849    858
 300   3029   3169   3054   2969   2960
1000  12032  11954  11941  12553  12266


Bubble-Sort

   N  Run 1  Run 2  Run 3  Run 4  Run 5

  10     66     47     93     82     64
  30    563    501    684    633    627
 100   6268   6918   6837   7474   6622
 300  62476  57756  ... you get the idea
1000  not tried, expected time ~600000..700000 clock ticks.

[wimoos]

The list of (float, int, string) variables is also interspersed with hooks to the DEF FNxx( ) functions.

More specifically, the bits 7s of the variablename are a flag for the datatype.
For a float, they both are 0. For a string, only the second is 1. For int, they both are 1. For FN, only the first is 1.

The value that is kept for the FN is a pointer to the function in the BASIC program.

So when you're defining a lot of those in the beginning of your program and hardly using them, be sure to DIM variables first.