Two additional articles online: Minimax & Sudoku
Message #1 Posted by Valentin Albillo on 26 July 2006, 4:40 a.m.
Hi all,
I'm taking my summer vacations in a few days, so I'll be
unable to access this forum or process e-mails till my eventual return a month or so from now. As a 'departing gift' I've put two of my recent Datafile
articles on line, in PDF format, for you to freely download
from my HP calc site. Both 'brief abstracts' follow:
Minimax Polynomial Fit
"By definition, the minimax polynomial is the approximating polynomial which has the smallest maximum deviation from the true function. Thus, we’re minimizing ABS(P(x)-f(x)) instead of (P(x)-f(x))2 ...
MMAXPOLY is a 50-line (w/o comments) program I’ve written to compute minimax polynomial approximations to any given set of data points. You can enter the data points directly from the keyboard, you can specify a generating function which will be evaluated in a given range to automatically generate the dataset, or you can read the dataset from a file. In the first two cases, the whole dataset can be stored in a file, for later retrieval and possibly further fitting or processing ...
MMAXPOLY allows the user to either specify a particular degree for the minimax polynomial, or else to give a maximum absolute error to be met, in which case it will iteratively compute a series of minimax polynomials for the given dataset, starting from degree 1 and incrementing it until either the maximum absolute error is equal or less than the one specified, or the degree is already N-1 (where N is the number of points in the dataset), which, rounding errors notwithstanding, would necessarily result in an exact fit (maximum error = 0 ) ...
Minimax polynomial fitting is an incredibly powerful technique to add to one’s own data-fitting arsenal. Though the internal details are complex enough and it does require a lot of computing muscle when compared to other well-known strategies such as Least Squares, the final reward is the improved accuracy it provides for any given degree or, conversely, the least possible degree for any given accuracy. It may take longer to compute the minimax polynomial, but typically you do that exactly once, then evaluate the resulting polynomial many times, which, being of lower degree than the ones obtained by other methods, will then execute faster and thus result in time savings in the long run."
Sudoku Solver’s Sublime Sequel
"This very small program, just 45 lines and well under 2 Kbytes of code (1898 bytes), will recursively solve any solvable Sudoku puzzle, fast. Carefully crafted, comprehensive 15-puzzle Test Suite included, which apart from showing this solver's performance in action can also be useful to you in order to test other solvers or even you own Sudoku abilities."
That's all, I hope you enjoy the articles. Happy summer vacations to all of you and
Best regards from V.
Edited: 27 July 2006, 3:57 a.m. after one or more responses were posted
|
Go back to the main exhibit hall