All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Ceiling and Floor Formulation (Posted on 2013-03-04)
Formulate an algorithm for fast evaluation of:
Σj=1,...,n2 (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

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 two ways of looking at the problem | Comment 2 of 6 |

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

 Search: Search body:
Forums (0)