File: TODO.txt

package info (click to toggle)
spigot 0.2017-01-15.gdad1bbc6-1
  • links: PTS
  • area: main
  • in suites: bookworm, bullseye, buster, sid, stretch, trixie
  • size: 904 kB
  • ctags: 1,521
  • sloc: cpp: 9,516; sh: 1,225; python: 643; makefile: 24
file content (136 lines) | stat: -rw-r--r-- 6,869 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
Possible future thoughts for spigot
===================================

This file is spigot's informal to-do list. I don't necessarily intend
to actually do all of these things; they're just thoughts and
ponderings, with discussion of the implementation strategy and/or
difficulties that I didn't want to lose having thought of them.

Waiting for input files to lengthen
-----------------------------------

Currently, the only two options when encountering EOF on an input file
are to bomb out with an exception, or to assume that means the number
represented is exactly accurate.

One could imagine finding uses for a third option, similar to 'tail
-f': if we see EOF, wait for more data to be added to the end of the
file, then read that and continue. Could be used in a situation where
another instance of spigot (or some other program) is in the process
of appending to the file in parallel with the one reading it.

Not sure how best to set it up, though; one would like to use some
kind of inotify-type facility, if available, to avoid the need to poll
tediously. And that's likely to involve a load of faff with
autoconf...

Interactive mode
----------------

spigot's command-line invocation is all very well if you want to pipe
lots of its output into something, but if you're using it for
interactive computation, it is a bit unwieldy, because it plays so
badly with Unix shell syntax and Unix command-line conventions - you'd
like to just type the expression you want to evaluate, but instead you
keep having to remember that some of them need to be single-quoted or
prefixed with '--' or both. It would be nice to also support an
interactive mode, with a nice readline-based command prompt, and some
means of controlling infinite streams of output, along the lines of
printing one line of digits by default and permitting some keystroke
like Tab at the command prompt to go back and add more data to the
previous computation. Then you could just type spigot-syntax
expressions directly at the command line, with no surrounding quoting
hassle.

The most hairy part of this idea is the bit where we come back from
the command prompt loop and need to generate more data from a spigot
that's stopped computing. Individual spigots' input sides are defined
as coroutines, but the system as a whole is not interruptible and
resumable at an absolutely general point, and would take some upheaval
to make it so. So this might be a feature that's most easily
implemented by C++11 multithreading - put each actual computation into
a std::thread, funnel its output back to the main loop via some
inter-thread data structure, leave it active but in a suspended state
if we might need to ask for more data later, and ask it to terminate
if not. Then the only upheaval you'd need would be to add a check into
every inner loop (of which there aren't all that many -
iterate_spigot_algorithm might even be the only one needed) so that
threads would know if they'd been asked to pause or stop.

There'd also need to be some sort of syntax available at the internal
command line to set all the same output and rounding options as are
available on the external command line, of course. And that syntax
would have to be impossible to confuse with an expression to be
evaluated.

Cleanups: memory leaks
----------------------

Quite a few of the top-level functions implementing spigot operations
do some preliminary checks for special cases, and if they find one,
just return some easy thing like spigot_integer(0). When that happens,
they ought properly to delete the spigot(s) they were passed as
operands, because those now won't be subsumed into the returned spigot
and hence won't be cleaned up when that gets deleted. It would be nice
to make a pass through all the code and sort those out.

(Especially if I ever do implement the interactive mode also mentioned
in this file - if spigot is going to run for longer than one
evaluation, it becomes more important not to leak memory.)

Cleanups: verify that matrices are refining
-------------------------------------------

In principle, more or less every matrix emitted by a spigot Source
should transform the starting interval into a (not necessarily proper)
subinterval of itself, rather than into a larger interval or an
interval that overlaps only part of the source interval.

On the rare occasion that that doesn't happen (typically because of
some anomalous starting matrix), we're supposed to have emitted the
'force' flag beforehand, to force the Source's consumer to absorb the
next matrix too so that we don't stop after a non-refining step.

It would probably be a good thing to add assertions to actually verify
that every time a Source returns with an unset 'force' flag, the
source interval actually _has_ been refined to a subinterval of
itself.

(This is probably more fiddly than it sounds, computationally: we'd
have to deal with the interval's image being mapped the other way up,
and forbid poles in the interval - except in the case of a pole at one
end if the starting interval extended to infinity anyway. Lots of ways
to get it wrong. Be careful.)

Experiment: evaluating transcendentals using a chain of Core2
-------------------------------------------------------------

spigot's method of evaluating a transcendental function f at an
irrational x works by evaluating f at a sequence of rationals
converging to x (typically much easier, because the underlying
implementation of f will typically be based on sequences of matrices
which represent rationals naturally), and combining the results using
MonotoneHelper to produce bounds on the value of f(x).

That's fine, and pragmatically seems to work. But Imperial College's
paper on _their_ exact real system suggests a different method, which
(translated into spigot terms) basically looks as if they lazily
construct an infinite chain of Core2, one for each element in the
series implementing f. So where I evaluate f at a rational by
generating a 2x2 matrix for each term of the series, they would
evaluate f at an irrational by generating a 4x2 Core2 tensor in each
case, with one of its inputs being a copy of the input x and the other
input being the next Core2 in the chain.

If I ever have leisure, it might be fun to give that strategy a try,
just out of sheer curiosity - to see if it works, and to see how it
compares in speed terms.

I think the way to do this in spigot would be: invent a class called
(say) LazySource. This would return its starting interval, wait until
it gets asked for a matrix, and _then_ construct a
SourceGenerator(Core2(x->clone(), another LazySource)), with the Core2
starting tensor derived from the series implementation of whatever
transcendental function we're computing. And the next LazySource that
we'd construct would contain enough mutated state to know that it's
the next term in the series.