Sum multiples of 3 and 5: Difference between revisions
→{{header|Forth}}: Add Fortran.
(→{{header|Forth}}: Add Fortran.) |
|||
Line 801:
1000000000000000000 233333333333333333166666666666666668 ok
</lang>
=={{header|Fortran}}==
The method here recalls the story of the young Gauss being set the problem of adding up all the integers from one to a hundred by a master who wanted some peace and quiet from his class. The trick here is to apply the formula for multiples of three and for five, then remember that multiples of fifteen will have been counted twice.
Early Fortrans did not offer such monsters as INTEGER*8 but the F95 compiler I have does so. Even so, the source is in the style of F77 which means that in the absence of the MODULE protocol, the types of the functions must be specified if they are not default types. F77 also does not accept the <code>END FUNCTION ''name''</code> protocol that F90 does, but such documentation enables compiler checks and not using it makes me wince.
<lang Fortran>
INTEGER*8 FUNCTION SUMI(N) !Sums the integers 1 to N inclusive.
Calculates as per the young Gauss: N*(N + 1)/2 = 1 + 2 + 3 + ... + N.
INTEGER*8 N !The number. Possibly large.
IF (MOD(N,2).EQ.0) THEN !So, I'm worried about overflow with N*(N + 1)
SUMI = N/2*(N + 1) !But since N is even, N/2 is good.
ELSE !Otherwise, if N is odd,
SUMI = (N + 1)/2*N !(N + 1) must be even.
END IF !Either way, the /2 reduces the result.
END FUNCTION SUMI !So overflow of intermediate results is avoided.
INTEGER*8 FUNCTION SUMF(N,F) !Sum of numbers up to N divisible by F.
INTEGER*8 N,F !The selection.
INTEGER*8 L !The last in range. N itself is excluded.
INTEGER*8 SUMI !Known type of the function.
L = (N - 1)/F !Truncates fractional parts.
SUMF = F*SUMI(L) !3 + 6 + 9 + ... = 3(1 + 2 + 3 + ...)
END FUNCTION SUMF !Could just put SUMF = F*SUMI((N - 1)/F).
INTEGER*8 FUNCTION SUMBFI(N) !Brute force and ignorance summation.
INTEGER*8 N !The number.
INTEGER*8 I,S !Stepper and counter.
S = 0 !So, here we go.
DO I = 3,N - 1 !N itself is not a candidate.
IF (MOD(I,3).EQ.0 .OR. MOD(I,5).EQ.0) S = S + I !Whee!
END DO !On to the next.
SUMBFI = S !The result.
END FUNCTION SUMBFI !Oh well, computers are fast these days.
INTEGER*8 SUMF,SUMBFI !Known type of the function.
INTEGER*8 N !The number.
WRITE (6,*) "Sum multiples of 3 and 5 up to N"
10 WRITE (6,11) !Ask nicely.
11 FORMAT ("Specify N: ",$) !Obviously, the $ says 'stay on this line'.
READ (5,*) N !If blank input is given, further input will be requested.
IF (N.LE.0) STOP !Good enough.
WRITE (6,*) "By Gauss:",SUMF(N,3) + SUMF(N,5) - SUMF(N,15)
WRITE (6,*) "BFI sum :",SUMBFI(N) !This could be a bit slow.
GO TO 10 !Have another go.
END !So much for that.
</lang>
Sample output:
<pre>
Sum multiples of 3 and 5 up to N
Specify N: 1000
By Gauss: 233168
BFI sum : 233168
Specify N: 1001
By Gauss: 234168
BFI sum : 234168
Specify N: 1002
By Gauss: 234168
BFI sum : 234168
Specify N: 1003
By Gauss: 235170
BFI sum : 235170
Specify N: 1000000000
By Gauss: 233333333166666668
BFI sum : 233333333166666668
</pre>
The result for a thousand million took about a minute for the brute-force-and-ignorance calculation. For much larger values of N, it should be discarded! Integer overflow even for 64-bit integers impends. The calculations could be conducted in double precision (or better, quadruple precision), a trivial modification to the source. Precise results would require the introduction of multi-precision arithmetic.
=={{header|Go}}==
| |||