logo To Foot
© J R Stockton, ≥ 2013-09-08

JavaScript Miscellany 0.

No-Frame * Framed Index * Frame This
Links within this site :-

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

Width of Text

Font :
Edit :
  Width : px
 

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  .

Making a Long String

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.

: Repeat Units
: Repeat Counts   Beware increasing length too much.
: Fast
: Slow
 
Time : s

Beetle totally changed, 2009-12-26.

Combinations and Permutations

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.

Elements All Distinct

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.

Elements Not All Distinct

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.

Array Methods

On Arrays

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.

Substitute Methods

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

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.

 
 Testing :    
Naturally slow for large numbers. Routine EratoB is slightly faster. The upper limit for EratoA & EratoB is given by the maximum number of elements in an array. Since the arrays store only Booleans, that could be extended by a factor of 54 (?) by bit-mapping into signed integers.

For the Estimate, see Prime Number Theorem.

Cacheing

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.

Factorial Recursion

 
 

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.

Ways of Giving Change

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.

Partition Numbers

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.

Partition Numbers
Cache On :
Range Min
Max
Home Page
Mail: no HTML
© Dr J R Stockton, near London, UK.
All Rights Reserved.
These pages are tested mainly with Firefox and W3's Tidy.
This site, http://www.merlyn.demon.co.uk/, is maintained by me.
Head.