Re: A reference implementation of text2interval - Correction
Sorry. I have correct my previous e-mail.
The statement A-ii and B-iii about detection l > u are valid only when
l and u are of the same radix, radix of rational p/q is 10.
The corrections are in upper case.
Thinking about the case wiht different radices...
-Dima
===============
I tried to summarize what is known about complexity of algorithms that may be used in
infsup-b64-text2interval(s) .
"n" is the length of s.
"Input stream" means that algorithm doesn't have random access to input string s.
"Input string" means that algorithm has random read-only access to input string s,
in this case "memory" is additional read/write memory.
"Accurate" means that the result is contained in
nextOut(infsup-b64-hull(level1-text2interval(s))) when l <= u and
that the result may be not empty when l < u.
"Tightest when l <= u" means that the result is
infsup-b64-hull(level1-text2interval(s)) when l <= u.
"Detects l > u WHEN THEY ARE OF SAME RADIX" means the result is always NaI when l > u and they are of the same radix.
"May not detect when l > u" means that
the result may be [f, nextUp(f)] instead of NaI
when f < u < l < nextUp(f) for some f \in b64
"Difficult programming" means that implementation need external libraries like libgmp.
A) Without rational literals.
i) Tightest when l <= u, may not detect l > u.
Input stream, O(1) memory, O(n) time.
ii) Tightest when l <= u, detects l > u WHEN THEY ARE OF SAME RADIX.
Input string, O(1) memory, O(n) time.
B) With rational literals.
i) Accurate
Input stream, O(1) memory, O(n) time.
ii) Tightest when l <= u, may not detect l > u.
Input string, O(1) memory, O(n) time.
iii) Tightest when l <= u, detects l > u WHEN THEY ARE OF SAME RADIX.
Input string, O(1) memory, O(n^2) time.
iv) Tightest when l <= u, detects l > u.
Input STREAM, O(n) memory, O(n log n log log n) time, difficult programming.
===================
-Dima