Browse Prior Art Database

High Speed Algorithm for Iota and Epsilon

IP.com Disclosure Number: IPCOM000052356D
Original Publication Date: 1981-Jun-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Gaston, CA: AUTHOR

Abstract

It is widely known that the APL operators, "Dyadic Iota" (X Iota Y) and "Dyadic Epsilon" (Y Epsilon X) become very slow as the vectors X and Y become long because the times required increase generally as the square of the size of the problem. The algorithms disclosed here provide a substantial speed advantage for certain classes of problems:

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 99% of the total text.

Page 1 of 1

High Speed Algorithm for Iota and Epsilon

It is widely known that the APL operators, "Dyadic Iota" (X Iota Y) and "Dyadic Epsilon" (Y Epsilon X) become very slow as the vectors X and Y become long because the times required increase generally as the square of the size of the problem. The algorithms disclosed here provide a substantial speed advantage for certain classes of problems:

There are two limitations to using these algorithms: (1) X and Y must be integers > or = Square IO (although in a primitive implementation, chara vectors could be handled easily) and (2) there must be sufficient workspace available to generate the indexing vector I (although in a primitive implementation, that space could be external to the active workspace).

In most applications the size of I (determined here by Gamma/X,Y) will be known a priori and need not be calculated. The reversal (Phi) is necessary only if there is a duplication in X.

These algorithms are particularly advantageous if the operation is done repeatedly with the same X but different Y vectors. The indexing vector does not change, so the first two lines need be performed only once.

The "indexing" approach disclosed here can be faster than the APL operators, even with arguments of length less than 100. With argument length and range approximating one million, the disclosed algorithms can perform the Epsilon or Iota functions in less than 10 seconds. By contrast, the primitive operators would require at least 150 hour...