=for advent_year 2008
=for advent_day 3
=for advent_title Sleighing big numbers
=for advent_author Bill Ricker
=head2 How Santa's IT Dept Saves Xmas (installment 2)
=head3 ATTN Comics Editors -- embargo Dec 3
Santa's Route planning department and his payload planning department have to work together. He does not have time to search through multiple sacks at each chimney for the right items, the sleigh needs to be loaded with the precision of a FedEx or UPS truck - the next present must be next to hand. So load and route sequence are inextricably linked.
We suspect the sleigh and reindeer must have elven teleport abilities (whether wormhole or other transdimensional passage or some anti-relativistic quirk), since the Classical acceleration required to make all the required stops in a mere A<../../2007/16/|30> to 50 hours (from International Date Line (IDL) date start to IDL date stop) is horrendous, and the sonic booms would have been reported. Besides, his time on station at each stop improves dramatically if both up-the-chimney and roof to roof are instantaneous.
Let's check the calculations on A's explanation.
Absolute precision is not required for optimization, they need plan and replan … B; and "the best" is the enemy of good enough. So the Elven planners and their Neptunian outsourced IT staff use M as an electronic sliderule for back-of-the envelope estimates when they fear blowout of floating point in their scripts (and A for interactive use).
Following A, we start with the UNICEF world child census and deduce the physics equation by equation.
=begin pre
2.106000e+09 children per unicef
8.424000e+08 stops (children/2.5)
3.141593e+00 pi
3.986000e+03 Re Earth radius, miles.
1.996570e+08 area sq. miles.
5.790052e+07 populated area (dry 29%) sq. miles.
6.873281e-02 area each, sq.miles / houses
2.621694e-01 mean distance, miles (sqrt area each)
2.208515e+08 mileage= houses * mean distance; miles
1.728000e+05 seconds total flight
2.051282e-04 Time between each, s
1.278076e+03 speed avg, miles/second
4.601074e+06 speed avg, miles/hr
4.601074e+06 speed avg, m/s (metric)
6.134765e+03 Mach - web page off x1000 !
3.000000e+08 C, speed of light, metric, m/s
1.458531e+02 ratio C:spd :: _:1
4.010885e+10 acceleration m/s/s
4.092740e+09 accel G's
1.914545e+12 Cargo grams
4.212000e+09 Cargo Lbs (2 Lbs/Child)
7.679021e+19 F=ma: Force, Newtons
1.7e+7153006998 traveling salesman, houses!
=end pre
We find the A slipped a decimal on Mach number, but otherwise holds up with assumptions given.
(Of course, out-sourcing delivery to various cultural gift bringers -
Befanna, Three Kings/The Magi, Grandfather Winter, Pere Noel, St Basil, Christ Child, Ste Lucia, Father Christmas, Old Man Frost, Tio Nadal (Uncle Xmas),
etc, greatly aids Santa's actual workload. And their team being able to do some households on St.Stephens Day or Three Kings Day or Solstice Eve or Lucia's Day also helps them all.)
Alas, even I the size of their un-structured Traveling Salesman problem as C takes 13 hours (47,212 seconds).
=for pre
fact 1e1 = 3628800 [0s]
fact 1e2 = 9.33262154e+157 [0s]
fact 1e3 = 4.0238726 e+2567 [0s]
fact 1e4 = 2.84626 e+35659 [0s]
fact 1e5 = 2.82423 e+456573 [1s]
fact 1e6 = 8.2639 e+5565708 [6s]
fact 1e7 = 1.202 e+65657059 [70s]
fact 1e8 = 1.62 e+756570556 [646s]
2.106000e+09 children
8.424000e+08 houses
traveling salesman
fact 842400000 = 1.6e+7153006998 [47212s]
=end pre
This is hyperexponential, I would have expected 2 hours.
So they have to replace M's Fact() with A when N is large enough that M:BA is barely keeping precision beyond order of magnitude anyway.
=for pre
fact 1e1 = 3598695.6187 [0s]
fact 1e2 = 9.32484763e+157 [0s]
fact 1e3 = 4.0235373 e+2567 [0s]
fact 1e4 = 2.846236 e+35659 [0s]
fact 1e5 = 2.82423 e+456573 [0s]
fact 1e6 = 8.2639 e+5565708 [0s]
fact 1e7 = 1.202 e+65657059 [0s]
fact 1e8 = 1.62 e+756570556 [0s]
fact 1e9 = 1 e+8565705523 [0s]
fact 1e10 = 2 e+95657055186 [0s]
fact 1e11 = 1 e+1056570551820 [0s]
fact 1e12 = 1359 e+11565705518100 [0s]
fact 1e13 = 1 e+125657055181000 [0s]
fact 1e14 = 1 e +1.35657055181 e+15 [0s]
2.106000e+09 children
8.424000e+08 houses
traveling salesman
fact 842400000 = 1.7e+7153006998 [0s]
=end pre
This performs in constant time, which is pretty good.
1.7e+7_153_006_998. Ten to the 7 Billion. That's large. That many routes to optimize between is obviously not going to be precisely solved! Can the Eleven Planners and Neptunian IT find a fast enough good enough approximation in time to save Christmas?
(To Be Continued)
=sourcedcode mod3.pl
=begin eds
Math::BigApprox certainly has its uses.
While for most purposes 1.797693e+308 DBL_MAX for 32 bit perl is quite adequate, there are times when the extended range of Math::BigWhatever is needed but not the costly precision. With the Stirling approximation, it did let me compute factorial 10^30 which is sometimes necessary.
=end eds