Kudos to Silverfrost

The following short program came out of a discussion at Fortran.Discourse.Group. When run, it reproduces the result from the 1966 paper by Lander and Parkin in 1966, which disproved the long-standing Euler Conjecture on the sum of fifth powers of integers. The current version of FTN95 compiles the program successfully. The 64 bit EXE runs in about 1 second, and outputs the expected result. Congratulations, Silverfrost!

!
   ! 27^5 + 84^5 + 110^5 + 133^5 = 144^5
   !
   program euler
   use, intrinsic :: iso_fortran_env, only: int64
   implicit none
   integer(int64), parameter :: nmax = 150
   integer(int64) :: i,j, k, l, m
   integer(int64) :: n5(nmax)

   outer: do i = 1, nmax
      n5(i) = i**5      !overflow when i=74
      do j = 1, i
         do k = 1, j
            do l = 1, k
               do m = 1, l
                  if ( n5(j)+n5(k)+n5(l)+n5(m) == n5(i) ) then
                     print *, 'i^5 = ', n5(i)
                     print *, j, k, l, m, i
                     exit outer
                  end if
               end do
            end do
         end do
      end do
   end do outer

end program euler

[Here is a link to the 1966 paper:](Here is a link to the 1966 paper:) https://community.intel.com/t5/image/serverpage/image-id/11600iD6EE41CC15A31C45/image-size/large/is-moderation-mode/true?v=v2&px=999&whitelist-exif-data=Orientation%252CResolution%252COriginalDefaultFinalSize%252CCopyright

Do we know how long the original program took to run?

Quoted from Robert Do we know how long the original program took to run?

Many questions about the CDC mainframes are very difficult to find answers for. We do not know what language the program was written in. Fortran, Cobol and the Compass assembly language were available. Nor do we know how they handled the large range of integers (up to 144^5) needed. The CDC used 48-bit floating point (60 bit register with 48 bit mantissa) arithmetic even for integer calculations. I do remember that compilations of even moderate-size Fortran programs took 1 to five seconds (not counting the time spent reading the card deck).

144^5 is 6.19e10 which is 36-bits of precision, although they would probably need more depending on how they used it. I suppose you could do it in 48-bits floating but the exponent and mantissa would have to be in the correct ranges.

I find the speed of mecej4's implementation compared to the (slightly modified) FORTRAN IV code from the rosetta code page shown below to be rather illuminating.

!$$$$$$ C EULER SUM OF POWERS CONJECTURE - FORTRAN IV
!$$$$$$ C FIND I1,I2,I3,I4,I5 : I1**5+I2**5+I3**5+I4**5=I5**5
!$$$$$$       INTEGER I,P5(250),SUMX
      INTEGER(4) I,P5(250),SUMX
      MAXN=250
      DO 1 I=1,MAXN
   1  P5(I)=I**5
      DO 6 I1=1,MAXN
      DO 6 I2=1,MAXN
      DO 6 I3=1,MAXN
      DO 6 I4=1,MAXN	  
      SUMX=P5(I1)+P5(I2)+P5(I3)+P5(I4)
      I5=1
   2  IF(I5-MAXN) 3,3,6
   3  IF(P5(I5)-SUMX) 5,4,6
   4  WRITE(*,300) I1,I2,I3,I4,I5
      STOP
   5  I5=I5+1
      GOTO 2
   6  CONTINUE
 300  FORMAT(5(1X,I3))
      END

Are you keeping us in suspense?

No, wrong choice of word on my part. Perhaps 'instructive' would be better.

The 'modern' implementation is x100 faster than the spaghetti code with its two arithmetic if jumps and goto in the inner loop.

Kenneth, there is a problem with the statement numbered 1 in your code: The expression 150^5 = 75937500000 is too large for assigning to the default KIND integer i.

We need 8-byte integers for that. That is one of the issues that puzzled me about how they wrote a program for the CDC 6600 without using more elaborate coding for multiple-precision arithmetic.

Mecej4,

Integer(4) is a 64 bit integer in FTN95.

use iso_fortran_env
integer(4) i
print*, compiler_version()
print*, huge(i)
print *, storage_size(i)/8   ! bytes
end

returns

 FTN95 v9.20
   9223372036854775807
            8

If I am wrong, please correct me!

Kenneth, you win. I often forget that integer(4) means integer of kind-number=4, and think that it is the same as the non-standard integer*4.

After compiling your program with NAG Fortran, with the -C=all -kind=byte options and running, i get the run time error:

Runtime Error: ks.f, line 7: Integer overflow for exponentiation 74**5

Mecej4,

The mistake you made (and I am surprised that you did, as you are my model for understanding Fortran's rules) is exactly why I detest KIND when the non-standard, but almost ubiquitous, REAL* description is so much clearer/

Merry Christmas!

Eddie

The wikipedia article on the CDC 6600 says 'The 6600's CP used a 60-bit word and a ones' complement representation of integers'

I think the wikipedia article is wrong as I recall for CDC 6600, integers were 48 bits in a 60 bit word and holerith was A10 and only 64 character values (no lower case) I recall how little I knew about memory size and variable precision at that time. I just assumed it would give the correct result ! After all, the alternative was a slide rule. The CDC 6600 was the second computer I used, after learning on an IBM, which taught me never to use IBM again.

I used the CDC 6400 at Imperial College both when I did my MSc there in 1971-2 and when I did my PhD 1976-80 (although the latter was part time). London University had a central computing unit with faster models, certainly a 6600. Imperial had what they called ‘Instant Turnround’ which meant that one queued up to hand over one’s deck of up to 600 cards, then stand and wait for a few moments to collect the printout that issued at high speed from a line printer. Instant Turnround users were allowed up to 6 seconds of CPU time! This included both compilation and runtime. Limitations on the number of cards meant very few comments in source codes and no backups – terminal access was a revelation. I used the CDC standard Fortran-66 compiler, MNF (which I think was Minnesota Fortran), but I do remember in about 1979 being shown something called FTN77 (which may have been a proposal rather than a finished product, because I never used it) although I do remember that it had ‘Hershey fonts’ (and hence Greek letters and maths symbols) in its graphics system. Now remember that the PC hadn’t been invented then, so there may be some part of Salford Fortran’s history that we have lost. The IC CDC 6400 had both Calcomp and Kingmatic plotters, and as I approached the end of the PhD they started to move towards terminal access, with graphics using Tektronix terminals and abandoning the ‘Instant Turnround’ service. I’ve forgotten now what the graphics library was, but it was certainly primitive. To be honest, I never gave precision much thought, just that the CDC’s 60-bit word was better for REALs than the 2x24-bit words on the Elliot/NCR 4120 I’d been using, and rather superior to the 2x16-bit words on a dreadful IBM 1130, and for what I was doing I never needed INTEGERs higher than a couple of hundreds, and never negative! John is right about A10, and the ‘no lower case’ is because a 6-bit coding was used. My experience of the 1130 also turned me off IBM mainframes. When doing my PhD I used to spend a lot of evenings after my normal day’s work, driving up to central London in my Lotus sportscar. At one point I was desperate to find some US standard thread screws (No 6 size) for the rear light fittings (Lotus obviously having bought a job lot intended for export from Lucas), which I eventually found with the aid of one of the night operators, in a discarded, worn out, CDC line printer that we dismantled!

I used the CDC 6600 at the University of Minnesota from 1970 to 1972. The compilers that I used in the beginning were RUN, FUN and FTN, all from CDC. RUN was the fastest to read and compile the Fortran source from your card deck. FTN was the slowest in that regard, but produced optimised code and gave the fastest runs of your program. FUN was in between RUN and FTN in both regards -- quite quick to compile, and good run times for user programs. Then MNF became available, and was better for students' program develoment because it gave good diagnostics and traceback. In 1972, I switched to Pascal on the UM CDC 6400, since Wirth had provided his compiler and Pascal fitted my needs better than Fortran at that time. The 6400 ran a time-sharing OS (KRONOS) with paper tape input and Teletype output, both very slow but the Teletype terminals were in the same building as my student office (significant advantage on snowy winter days, with ice-glazed concrete walkways between buildings). My first encounter with a computer was in 1968, on an Elliot 804 Mark II, with paper tape input, line printer output. the programming language was 'Autocode', and debugging was helped by a speaker that was fed a certain bit from the computer. One learned to detect from the groaning sound that a specific segment of the program was being executed. I used a CDC 3600 in 1968, an IBM 1620 in 1970, IBM 360s in 1976 and 1977, Univac 1110 in 1976, Honeywell6000 and a Hitachi IBM360 clone later. Then the university that employed me switched to DEC and AT&T computers. Then PCs became available and the whole way of computing changed.