Re: Add nested-function support in a language the based on a stack-machine

On 19/03/18 19:50, Gene Wirchenko wrote:
>> Faster machines and larger memories mean that it becomes more
>> important to use the best algorithms.
>
> How does that follow?


It follows because data expands to fill the memory available.


> One could argue exactly the opposite as there are resources to
> waste.
>
> [Depends on the algorithms. If they're linear, things are fine, not
> so fine if they're O(N^2) or O(2^N) -John]


My first computer had 8K of RAM and a 1MHz clock speed.
If I wanted to sort 1,000 values I could use bubble sort, O(N^2),
or quicksort, O(N log N).


So, bubble sort would need of the order of 1,000,000 instructions
and take about 1 second: this might well be acceptable for an operation
you only need to do a few times an hour. Quicksort would need
of the order of 10,000 instructions and take 0.01 seconds.


My current laptop (not the latest model) has 8Gb of RAM:
literally, over a million times as much RAM, and a 1.7 GHz clock.
Even accounting for more powerful instructions, the clock is
only of the order 10,000 times faster, while the memory is 1,000,000
times larger. Now 1,000,000,000 values will fit in RAM.
Sorting these with bubble sort will need of the order 10^18 instructions
which takes 100,000,000 seconds (over 1,000 years) while quicksort
needs 300,000,000,000 instructions and takes only a few seconds.


For a linear algorithm, say a linear search, my first computer
takes 0.001 seconds to process the data, while my new laptop
takes 0.1 seconds. So if I need to execute this linear algorithm
more than 10 times a second, my old computer will be fine
but my new laptop would struggle. I would need to look hard
for a sub-linear algorithm.


Conclusion: even for linear algorithms things may not be fine
and more powerful sub-linear algorithms may be needed.


--
Martin


Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4
[Give or take the detail that bubble sort is never the right algorithm
since insertion sort is shorter and faster, I agree. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.