© J R Stockton, ≥ 2013-09-08

Links within this site :-

**Merlyn Home Page**- Site Index, E-Mail, Copying**JavaScript**:-- Index and Introduction - with About This Site, Code Re-use, Links
**This Page**:-- Miscellany 1
- Tests
- Rounding
- Maths
- Exact Arithmetic (NEW PAGE) :-
- Include Files

**See** "About This JavaScript Site" in
JavaScript Index and Introduction.

Put HTML in the Edit control, and press the button. Unicode
characters can be inserted in decimal as, for example,
`ӂ`. To determine the value of am em unit in the given
or default font, insert ` `.

Function `BigCat` is efficiently recursive - `Wombat`
is an iterative equivalent. And `EjHCat` is cunning. Note the
differing behaviour of the various routines when the repeat unit is
longer than one character.

`Beetle` totally changed, 2009-12-26.

N.B. The underlying algorithms are, probably, more or less, the simplest; likewise the actual code. But the code is not necessarily optimum, and the structuring of the details could be rather different in other languages.

More complex routines cacheing intermediate results can be substantially faster.

Recursive functions `Combs` and `Perms` combine and
permute `N` elements of `Src` at a time into `Got`
in all ways.
Array `All` collects the results, for which Function `Fn`
is an example.

Two ways of collecting selections in `Got` are shown.
In `Perms` character elements are concatenated into a String.
In `Combs` elements are treated as full Objects and
pushed onto an Array (but converted into a plus-separated string
in `Fn` for display here).

In these, array-handling efficiency has not been considered.

The set of permutations of "Mississippi" is the set of permutations of sorted "Mississippi" ("Miiiippssss"), and sorting is fast enough.

So first sort the input, then after `for (;;)` insert code for
*but only if this element differs from the previous* - in other
words, where successive available elements are indistinguishable,
only one should be a candidate.

In simple usage, an array `Arr` can be initialised like
`Arr = [3,"4",5]` to have `Arr.length` = 3 elements
`Arr[0] Arr[1] Arr[2]`. The elements can be of any type
and can differ in type; an "index" does not have to be an integer.
Actually, an Array is an Object with extra properties.

The `.length` property of an array is read/write. It does not
represent the number of elements currently defined in the array, but is
related to the numbering of the elements with non-negative integer
indexes.

The constructor `new Array(N)` sets the length to `N`
(rounded towards zero, then considered as unsigned 32-bit).

When a value is given to an element with a non-negative integer
index, and `.length` is not already greater than that index,
JavaScript makes it one greater than that index.

Writing to the `.length` property drops any elements with
integer indexes of that value or above.

`String(A)` shows just the integer-indexed elements,
comma-separated, from zero to `.length-1`, with undefined
elements showing as empty substrings.

Approximately.

These are substitutes for methods provided in current systems but not in MS IE 4.

Note that a truly general-purpose substitute method must be at least one of two things : fully compliant under all circumstances with the ECMA standard, and/or fully compliant under all circumstances with the behaviour of the majority of common browsers.

However, when a substitute method is used on a particular page or site it is only necessary that it complies with the user's expectations in the circumstances in which it can actually be called. For example, it may be guaranteed that the arguments are in the obvious range, that the array is non-empty, etc.

A substitute method that is known to be different should be given a distinct name.

To be tested more? :-

Needs much more testing.

The Sieve of Eratosthenes is a classical, intrinsically fast method for listing prime numbers; see also the Sieves of Atkin and Sundaram ; and Prime Numbers.

For the Estimate, see Prime Number Theorem.

Work should be repeated as little as possible. Intermediate results required repeatedly should be determined once and referenced as required.

Poor : document.getElementById("Fred").rows = 3 document.getElementById("Fred").cols = 66 Good : f = document.getElementById("Fred") f.rows = 3 ; f.cols = 66 Good : with (document.getElementById("Fred")) { rows = 3 ; cols = 66 }

Also, code should be repeated as little as possible; so use functions for such code, if as above will not suffice.

I've not speed-tested; but, except for light use, cached should beat iterative and recursive. It's substantially equivalent to using a lookup table, except that the table it generates is just as long as is needed, and no more.

A better example of cacheing follows.

JAD's Quiz 1995, question #14 - to determine the number of ways (49) to give change, in stated coin of the realm (50, 20, 10, 5 pence), for a given "Total" amount (£1.00).

Translated to JavaScript from Pascal program jad_9514.pas :-

The elements of "Coins" ought to be positive integers in strict descending order. That order was intended at design time; but now it seems to affect mainly speed when cache is used. The commas are essential, the spaces optional.

"Info" shows something of what the code has done. It does NOT show all of the acceptable results. It should ONLY be used for small numbers.

For £1.00 = 100p, cacheing intermediate results changed the time taken from intolerable to imperceptible in Borland Pascal on a 486dx/33.

Note the performance gain here with `Cache` set; allow for the
resolution of timing.

If "Coins" above is all of the integers from "Total" down to 1, inclusive, then the result "Ways" is the number of Partitions of the number "Total". The Partition checkbox above automates that setup.

Because of the limitations of IEEE Doubles, JavaScript Partition results will be inexact past PN(299) = 8620496275465025. With Cache above, PN(1000) = 2.4061467864032615e+31 in 3.8s using Chrome 8.0 on P4/3G.

The following code is simplified for partitions-only, and has more
cacheing, to list the partitions of successive integers more
efficiently. NOTE that the code does not clear the cache - use the
button for that. *CAVEAT : this code is costly in cache space, and the
improvement in cacheing gives relatively little extra benefit.*