Formulate an algorithm for fast evaluation of:
Σ_j=1,...,n² (floor (√j) + ceil (√j)), where n is a positive integer.

** ceil(x) is the least integer ≥ x and, floor(x) is the greatest integer ≤ x

Three approaches to a straightforward algorithm are:

DEFDBL A-Z
FOR trial = 1 TO 5
    t = TIMER
    FOR n = 400 TO 440
        tot = 0
        FOR j = 1 TO n * n
            tot = tot + INT(SQR(j)) - INT(-SQR(j))
        NEXT
        'PRINT n, tot
    NEXT
    PRINT TIMER - t
NEXT trial
PRINT: PRINT: PRINT

FOR trial = 1 TO 5
    t = TIMER
    FOR n = 400 TO 440
        tot = 0
        FOR j = 1 TO n * n
            sr = INT(SQR(j))
            IF sr * sr = j THEN
                tot = tot + sr + sr
            ELSE
                tot = tot + sr + sr + 1
            END IF
        NEXT
        'PRINT n, tot
    NEXT
    PRINT TIMER - t
NEXT trial
PRINT: PRINT: PRINT

FOR trial = 1 TO 5
    t = TIMER
    FOR n = 400 TO 440
        tot = 0
        FOR j = 1 TO n * n
            sr = INT(SQR(j))
            tot = tot + INT(sr) - INT(-sr)
        NEXT
        'PRINT n, tot
    NEXT
    PRINT TIMER - t
NEXT trial
PRINT: PRINT: PRINT

The timing trials for the 5 trials of 41 each come out to the following in QB4.5:

 

 3.68359375
 3.73828125
 3.6796875
 3.73046875
 3.73828125

 

 4.72265625
 4.77734375
 4.78125
 4.71875
 4.78125

 

 5.390625
 5.4296875
 5.390625
 5.4296875
 5.390625
 
Clearly attempts to speed things up just made for longer times.

However in QB64, the following times resulted:

 .98828125
 1.04296875
 .98828125
 1.046875
 1.04296875

 

 .55078125
 .546875
 .55078125
 .60546875
 .546875

 

 1.265625
 1.31640625
 1.265625
 1.26171875
 1.3203125

Clearly the second version was almost twice as fast as the original when using QB64.

However, the big deal in changing the algorithm comes from looking at the results for the first few numbers:

n             sum
1             2
2             12
3             38
4             88
5             170
6             292
7             462
8             688
9             978
10            1340
11            1782
12            2312
13            2938
14            3668
15            4510
16            5472
17            6562
18            7788
19            9158
20            10680
21            12362
22            14212
23            16238
24            18448
25            20850
26            23452
27            26262
28            29288
29            32538
30            36020
31            39742
32            43712
33            47938
34            52428
35            57190
36            62232
37            67562
38            73188
39            79118
40            85360

The first few sums are

2, 12, 38, 88, 170, 292, 462

Sloane's OEIS calls the sequence A035597 and gives the formula

(4 * n ^ 3 + 2 * n) / 3

then:
 
FOR trial = 1 TO 5
    t = TIMER
    FOR n = 400 TO 440
        tot = (4 * n ^ 3 + 2 * n) / 3
    NEXT
    PRINT TIMER - t
NEXT trial

shows time results as all zeros: so fast as to be immesurable by means of the TIMER function. Thus this is the best algorithm.

Posted by Charlie on 2013-03-04 15:27:36