John Tuttle
Recycles dryer sheets
- Joined
- Mar 7, 2006
- Messages
- 73
The thread on PC vs Mac reminds me that arguing over the merits of these two systems is a little bit like finding fault with a talking dog because it uses incorrect grammar. Either of these two machines is incredibly more powerful and easier to use than computers used by large research universities 30 years ago. Here is a small personal example.
The Postage Stamp Problem.
An envelope may carry no more than h stamps, and one has available k integer-valued stamp denominations. Given h and k, find the maximal integer n=n(h,k) such that all integer postage values from 1 to n can be made up. For example, n(3,6)=52 and the two solutions are (1,4,6,14,17,29) and (1,3,7,9,19,24). This means that every integer from 1 to 52 can be written as a sum of 1,2, or 3 of the integers (1,4,6,14,17,29) with repetitions allowed. Moreover, no longer sequence is possible satisfying the given conditions. Also, n(3,7)=70 with a single solution (1,4,5,15,18,27,34).
http://en.wikipedia.org/wiki/Postage_stamp_problem
This problem goes back at least to 1937. I first heard about it in 1974 and wrote a program to solve it. Over the years I have implemented the algorithm in FORTRAN, IBM 370 Assembler, Pascal, C, FORTH and C++. Some results for n(3,7) are summarized in the following table:
Year Computer/Chip Language Time (seconds)
1974 IBM 370/158 Fortran 45
1974 IBM 370/158 Assembler 15
1984 Apple ][/6502 FORTH 21,600
1990 Mac SE 8 MHZ 68000 Think Pascal 276
1990 16 MHZ 386SX Turbo C++ 53
1994 90 MHZ Pentium Visual C++ 1.5
1998 400 MHZ Pentium II Visual C++ 0.25
The IBM 370/158 was a large mainframe and was the main academic computer for the University of Illinois at Chicago. It filled a large room, RENTED for $50,000.00/month and an IBM systems engineer had his own on site office.
The algorithm is a good test of raw CPU speed since it is branch and bound with mostly simple integer arithmetic and array subscripting completely contained in memory.
The algorithm time increases exponentially. For kicks I tried n(3,8) and n(3,9) on my 2.8Ghz Dual Core Pentium with times of .55 seconds and 12.4 seconds.
The Postage Stamp Problem.
An envelope may carry no more than h stamps, and one has available k integer-valued stamp denominations. Given h and k, find the maximal integer n=n(h,k) such that all integer postage values from 1 to n can be made up. For example, n(3,6)=52 and the two solutions are (1,4,6,14,17,29) and (1,3,7,9,19,24). This means that every integer from 1 to 52 can be written as a sum of 1,2, or 3 of the integers (1,4,6,14,17,29) with repetitions allowed. Moreover, no longer sequence is possible satisfying the given conditions. Also, n(3,7)=70 with a single solution (1,4,5,15,18,27,34).
http://en.wikipedia.org/wiki/Postage_stamp_problem
This problem goes back at least to 1937. I first heard about it in 1974 and wrote a program to solve it. Over the years I have implemented the algorithm in FORTRAN, IBM 370 Assembler, Pascal, C, FORTH and C++. Some results for n(3,7) are summarized in the following table:
Year Computer/Chip Language Time (seconds)
1974 IBM 370/158 Fortran 45
1974 IBM 370/158 Assembler 15
1984 Apple ][/6502 FORTH 21,600
1990 Mac SE 8 MHZ 68000 Think Pascal 276
1990 16 MHZ 386SX Turbo C++ 53
1994 90 MHZ Pentium Visual C++ 1.5
1998 400 MHZ Pentium II Visual C++ 0.25
The IBM 370/158 was a large mainframe and was the main academic computer for the University of Illinois at Chicago. It filled a large room, RENTED for $50,000.00/month and an IBM systems engineer had his own on site office.
The algorithm is a good test of raw CPU speed since it is branch and bound with mostly simple integer arithmetic and array subscripting completely contained in memory.
The algorithm time increases exponentially. For kicks I tried n(3,8) and n(3,9) on my 2.8Ghz Dual Core Pentium with times of .55 seconds and 12.4 seconds.