[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Sudoku puzzle solver for Apple II
Bryan Parkoff wrote:
"Michael J. Mahon" <mjmahon@aol.com> wrote in message
XtudnVI15qUVVCnZnZ2dnUVZ_oydnZ2d@comcast.com">news:XtudnVI15qUVVCnZnZ2dnUVZ_oydnZ2d@comcast.com...
Scott Hemphill and I recently collaborated to create a Sudoku puzzle
solver for Apple II computers. The machine language solver is Scott's,
with some adaptations by me, and I wrote the interactive Applesoft
front-end.
SUDOKU runs on any Apple II with 80-column firmware and a 65C02
processor, which includes the IIc, the IIc+, the Enhanced //e, and
the IIgs.
It is amazingly fast! Most Sudoku solvers run on modern PCs thousands
of times faster than a 1MHz Apple II, and take seconds to solve a
puzzle, but Scott's solver is so time and space efficient that it
solves puzzles in seconds *running on an Apple II*!
Check it out at:
http://members.aol.com/mjmahon/Sudoku.html
It is available both as a ShrinkIt disk archive and as a .dsk image.
Enjoy!
(BTW, the execution profile referred to in the paper has not yet
been uploaded, so for the time being, that's a 404. ;-)
-michael
Fast Sudoku solving for Apple II's!
Home page: http://members.aol.com/MJMahon/
"The wastebasket is our most important design
tool--and it is seriously underused."
Michael,
I understand that space saving memory and efficient optimization on
6502/65C02 processor is best choice. How do you assume that optimized
Sudoku solving writted in x86 assembly and 6502/65C02 assembly might have
the impact speed? Is it possible that x86 assembly runs at 1GHz might be
faster or almost close to the same speed to 6502/65C02 assembly at 1MHz?
Surely you jest!
x86 code would be approximately as efficient in terms of space and ops
required to get to a solution, but would execute those ops about 6000
times faster! In fact, Scott's compiled C code for the algorithm solves
the 'evil01' puzzle in about 2 milliseconds, while a 1MHz Apple II takes
about 20 seconds--so there's a factor of 10,000.
One paragraph of your website states that optimization is evil. I guess
that many programmers and designer of processor are not smart enough to
study space saving memory and efficient optimization when they should try to
write algothrims in smaller functions.
"*Premature* optimization is the root of all evil" is a well-known
software engineering aphorism. It refers to the fact that a well-
structured but inefficent program can be optimized later without much
difficulty, but a program that has become twisted and "spaghettified"
in an effort to speed it up a little is very difficult to improve--and
most big improvements are algorithmic or data structure related, not
just coding hacks.
The meaning of the aphorism is to refrain from optimizing until you have
a reasonably well-structured program actually running. Then you can
measure it and determine exactly which 10% of it actually makes a real
difference in its efficiency. Optimization isn't bad, but optimizing
before you know what to optimize or why it matters is *very* bad. It's
a waste of time and it hardens otherwise malleable code.
I expect them to spend extra time and money to write advanced x86
assembly rather than high level language so they can write PC Operating
System and games. They can outperform better. It is wasting time and money
to develop modern x86 processors by trying to improve and increase the speed
while they forget all the optimization. It is too much dependant on speed
without optimization so software may operate little fair or poor speed.
As you know from my previous posts, I really lament the passing of the
age of craftsmanship in most software projects. But I also recognize
that the vast majority of code that is written is executed very seldom
if at all (think about the percentage of code that is error recovery
code). It is unreasonable to expect that most of the large applications
that we use today would be written in assembly language. (However, I
would like to see measurement-targeted dynamic optimization flourish--
maybe in another decade...)
How could you predict if improved processor under the design of 6502 may
run at 1GHz with 32 bits and 64 bits? They may have better space saving
memory and efficient speed than x86 processors. If it does exist,
programmers may expect modern emulator projects to be written in 6502
assembly might be slower than x86 processor like RISC processor. Do you
expect?
There could hardly be a more apples and oranges comparison. The 6502
architecture is very different from the x86 architecture in *many* ways.
The efficiency of a computer architecture is not an absolute, but is
completely relative to the nature of the workload that it will process,
and the cost point which it must satisfy.
For two very similar architectures, or for two implementations of the
same architecture, relative evaluations are much simpler, but are still
based on predetermined workload samples.
In the case of the Sudoku solver, I think that the empirical ratio of
performance between a 1MHz 6502 and a 3GHz 4-way superscalar x86 is in
rough agreement with their expected op throughput. Of course, the 6502
requires much less hardware to achieve its performance, and could, in
principle, run 20-50 times faster with essentially the same logic design
in modern technology, but that is all speculation.
-michael
Fast Sudoku solver for Apple II's!
Home page: http://members.aol.com/MJMahon/
"The wastebasket is our most important design
tool--and it's seriously underused."