Re: Solution to 7 over sqr(71) time against integer polyrhythms

[mclaren]

It's pretty clear from the nature of the bugs that there was some internal
rational integer calculation limit in lilypond. What's baffling is the way
it's dealt with internally in lilypond. The procedure seems to be to do
everything in 32 bit integers and then throw an error if that limit gets
exceeded.  Moving to 64 bit integers would extend the range of possible
musical inputs, but David Kastrup is right -- not by much. 2 x 10^19 as
opposed to 4 billion for 32 bit ints.

This is the way video games tend to deal with this stuff. They use 32 bits
integers or 64 bit integers and that's typically good enough for the game
spaces they're dealing with.  But video games have the same problem of
recursion when they calculate light bounced off  multiple reflective
surface, so they use a better way to deal with this stuff than just chugging
away forever and throwing an error. They cheat.

A long time ago I had to work on an 8 bit microcontroller and write my own
floating point routines.  With the small amount of RAM and the slow CPU
speed (4 MHz back then), you quickly started to throw errors. The better
solution seems like figuring out what a practical integer limit is and then
dump the intermediate result into floating point, then recast as an integer
on the final output. The range of floating point values is large, somwhere
in the ballpark of 1 x 10^300 if memory serves. You typically don't run into
those limits unless you encounter really exotic situations.

Let's take 50 nested tuplets of 100:99.  That's obviously (99/100)^50.
Pretty clearly you're going to run into 32-bit integer limits if you try to
calculate that directly because 2^32 = 4,294,967,296.  Nowhere near 100^50. 
Even 2^64 is only 1.8446744e+19, once again nowhere near 100^50. But why do
you need to calculate 100^50 directly?  What's the maximum timebase you'll
ever need for MIDI?  384 parts per quarter note?  What's the maximum tempo
you're ever going to want to run at?  Say, mm = 300?  You can do a Fermi
estimate here on the maximum time resolution that you would need to get less
than a millisecond error after 1000 measures, and I guarantee it's a lot
less than 100^50. I get something in the ballpark of 384*300*1000*1000.
Nowhere near 100^50.  When your fixed integer intermediate result
approaches, say, 1 x 10^18, cast it into a float, keep going, then recast
into a fixed integer again for the final result. 

What's the maximum size score Lilypond supports?   Broadsheet, which turns
out to be two stacked tabloid sheets, so 22 x 17.  What's the maximum dpi
you'd ever want to output at?  Say 2400 dpi. So you need 22 x 2400 x 17 x
2400 and your output raster resolution, which once again is wayyyyyyyyy
smaller than 100^50.  
These integers are the only ints lilypond should be worrying about.  Those
are final resolution limits in time for MIDI and in graphical resolution for
large broadsheet or tabloid output. There is no point in trying to do exact
calculations of 100^50 at the intermediate stage before the final answer. It
doesn't matter whether your moments are integers. If you need to turn the
note position into an integer moment value, recast the float a back into an
integer for the final moment value. That's the efficient way to do it.

Listen, my hand calculator can multiply .99 by itself 50 times and come out
with an answer. My hand calculator does not have 4 gigs of RAM and my hand
calculator does not have a dual core CPU and my hand calculator does not run
tons of scheme code, so it is definitely possible to do these kinds of
calculations reasonably quickly, without tons of RAM, and without rewriting
gigabytes of code. And my hand calculator does it without throwing an error
message. The way you get these kinds of calculations to run fast is by
throwing away precision at the tail end of the float and recasting into
integers periodically. This builds up error, but not a lot. My hand
calculator does give an error if you take 2^64. It does not give an exact
value, but an approximation, albeit accurate to about 10 decimal places. I
can live with that. That's good enough to work with in the real world.  It's
certainly good enough to output a MIDI stream accurate to within 384 ticks
per quarter note, and to output a double tabloid page of score at 2400 dpi. 
The MIDI might be off by one or two ticks every once in a while. That's
inaudible. The score might be stretched or distorted by 1 dot in 2400 per
inch. Big deal, nobody will see it.  

Look, what I'm saying is neither stupid nor pointless. It comes out of
personal experience. The people who ran the Manhattan Project did
calculations for the first nuclear bomb with a computer that had a lot less
than 32 kilobytes of RAM.  You can get around fixed-point limitations by
storing intermediate results as floats with some error remainder, recasting
the floats into integers as necessary and wherever necessary taking the
error remainder into account, and dumping the final output into whatever
integer time resolution or integer dpi resolution you need.  There are much
much better ways to handle these kinds of calculations than just plugging
along and saying, "Okey doke, let's just take 99/100 to the 50th power and
see what we get."  You multiply .99 by itself however many times the nested
tuplets require and when you get below the range of visible dpi or the
audible MIDI time resolution of say, 1 millisecond off every 100 measures,
you call the result zero and ignore further calculations because they don't
get you anywhere.  It's exactly the same as the perturbation method in
numerically solving differential equations. When you've gotten to 3 or 4
terms of a Taylor Series expansion, your errors are typically so low that
you don't need to bother calculating a 5th or 6th term. You just accept the
approximation as good to within one part in a million or whatever, spit out
an answer, and move on. 





--
View this message in context: 
http://lilypond.1069038.n5.nabble.com/Solution-to-7-over-sqr-71-time-against-integer-polyrhythms-tp196671p196746.html
Sent from the User mailing list archive at Nabble.com.