Martin Truebner wrote:
| All that POP has is the seconds in a table.
This is entirely correct; but, taken with their associated dates, it is enough.
Let us represent Gregorian dates as eight-character strings in a
'yyyymmdd' format.
>From the PrOp this table (extended) is
date, accumulated leapsecs
19000000, 0
19720701, 1
19730101, 2
19740101, 3
19750101, 4
19760101, 5
19770101, 6
19780101, 7
19790101, 8
19800101, 9
19810701, 10
19820701, 11
19830701, 12
19850701, 13
19890101, 14
19900101, 15
19910101, 16
19920701, 17
19930701, 18
19940701, 19
19960101, 20
19970701, 21
19990101, 22
20060101, 23
20090101, 24
20120701, 25
Such a table is best treated using not match-seeking but glb-seeking
binary search., i.e., a species of binary search that yields the
largest element in this ordered table of dates that is not greater
than the search argument, the greatest lower bound on this search
argument in the table. (All binary-search schemes are of course
similar, but "le bon Dieu--et donc aussi le diable--est dans le
détail".)
For clarity I illustrate this scheme in PL/I:
ymdsglb: procedure(DLSTp, sarg, leapsecs)
returns(aligned bit)
reorder ;
/* Given a Gregorian date in 'yyyymmdd' formatSets the argument
corresponding to the parameter leapsecs equal to the total number
of leap seconds inserted into the Gregorian calendar before that
date and returns '1'b, true, if the search argument is bounded, i.e.,
iff the value of sarg is not less than that of the lowest element in the
table. Returns '0'b, false, if the search argument is not bounded. */
declare (DLSTp) pointer nonassignable, /* -> DLST */
sarg character(8) nonassignable, /* search argument, 'yyyymmdd' */
leapsecs signed binary fixed(15,0) assignable) /* leap seconds */
parameter ;
declare 1 DLST based(DLSTp), /* table to search */
2 eye character(4), /* 'DLST' */
2 tls signed binary fixed(15,0), /* low table-element subscript */
2 ths signed binary fixed(15,0), /* high table-element subscript */
2 tab dimension(0 refer(DLST.tls):1 refer(DLST.ths))
3 edt character(8), /* effective date, 'yyyymmdd' */
3 cls signed binary fixed(15,0) ; /* leap-second count,
cumulative */
declare (F1 value(1b), F2 value(10b)) signed binary fixed(7,0) ;
declare (hi, himin, lo, mi) signed binary fixed(31,0),
(bounded, iterate, search_higher) aligned bit ;
lo, himin = DLST.tls ;
hi = DLST.ths ;
do iterate = (lo ¬> hi) repeat(lo ¬> hi) while(iterate) ;
mi = lo + (hi - lo)/F2 ;
search_higher = (sarg >= DLST.tab.edt(mi)) ;
if search_higher then lo = mi + F1 ;
else hi = mi - F1 ;
end ;
bounded = (hi ¬< himin) ;
if bounded then leapsecs = DLST.tab.cls ;
return(bounded) ;
end ymdsglb ;
for the canonical n + 1 = 26 + 1 = 27 search arguments for glb-seeking
search in this table, 15 will require 4 comparisons and 12 will
require 5, a mean of (15 x 4 + 12 x 5)/27 = 4.4444 comparisons per
search.
There are other, equally legitimate numbering/subscripting schemes for
leap-second dates that differ from the one used in the PrOp. It all
depends upon what point in time one chooses as an epoch origin for
them,
John Gilmore, Ashland, MA 01721 - USA
