RE: Another proposal for a "split" function to complement "mid"
will it be a concern that asinh requires computing ln which is much slower than usual midpoint and most the alternatives propsed so far?
also, sounds somewhat arbitrary -- if someone can empirically check that this particular function works well (and better than other functions with a similar asymptotic behavior) that would make this proposal much more convincing -- and it will probably be possible to come up with a theoretical explanation
________________________________________
From: stds-1788@xxxxxxxx [stds-1788@xxxxxxxx] On Behalf Of John Pryce [prycejd1@xxxxxxxxxxxxx]
Sent: Sunday, March 18, 2012 10:02 AM
To: Dan Zuras Intervals
Cc: stds-1788
Subject: Another proposal for a "split" function to complement "mid"
Dan, P1788, also Arnold, Baker and Nate
On 14 Mar 2012, at 17:22, Dan Zuras Intervals wrote:
> I have been contemplating that split function we discussed
> earlier. In so far as is possible, I would like to write
> it independent of the underlying interval form. In effect,
> not caring whether one uses explicit (inf-sup or [a,b] form)
> or implicit (mid-rad or <m,r> form).
I personally am against the idea of a Level 2 mid(xx) function that gives non-NaN values for intervals xx = [xlo,xhi] such that the Level 1 value is undefined.
But I see the need for a split(xx) function for those who do Branch & Bound and similar work.
Arnold proposed a "median" idea based on finding a value xmed such that there are about as many FP numbers between xlo and xmed as between xmed and xhi, but has dropped it for the present. Dan is thinking along similar lines, but his method seems to be parameterized by the FP radix, which doesn't appeal to me much.
Can I propose a more mathematically based "median"? It's parameterized by a single number L>0, a "length scale", which the user chooses to suit the application. Like the other proposals, it is symmetric round 0, and:
- If |xlo|, |xhi| are somewhat < L, it is almost
the same as arithmetic mean.
- If xlo somewhat > L, or xhi somewhat < -L, it
is almost the same as geometric mean.
The idea is to use the asinh(x) function, which is like x for |x| small, like log(x) for x somewhat > 1, and like -log(-x) for x somewhat < -1. You transform from the x variable to a y variable by
Divide by L to fit the length scale,
Take asinh.
You take the arithmetic mean in the y variable and transform back to the x variable by
Take sinh,
Multiply by L.
Here is Matlab code. If the implemented functions asinh and sinh are (weakly) monotone, the returned value is guaranteed to lie in [a,b], no matter how narrow it is.
%--------------------------
function m = fmedian(a,b,L)
a1 = asinh(a/L);
b1 = asinh(b/L);
m1 = a1 + 0.5*(b1-a1);
m = L*sinh(m1);
%--------------------------
Here is a little test program, which simulates the Bisection Algorithm:
%-----------------------------------------------------------------------
function Tfmedian(a,b,L,probLR,niter)
% Repeatedly find the FMEDIAN, c, of interval [a,b] and replace [a,b] by
% [c,b] with probability probLR, otherwise by [a,c]. Do it NITER times.
% So it's a pseudo bisection method.
% Special cases: probLR=0 always "moves left", probLR=1 "moves right".
fprintf(1,' a=%14.6f b=%14.6f\n',a,b);
for i=1:niter
m = fmedian(a,b,L);
if rand<=probLR
a = m; str = 'right';
else
b = m; str = 'left ';
end
fprintf(1,'%5s, a=%14.6f b=%14.6f\n',str,a,b);
end
%-----------------------------------------------------------------------
Below are results of four runs, with [a,b] = [0,1e6] and the length scale L = 1, 1e2, 1e4, 1e6 in turn. I took probLR=0.5, so it is equally likely to keep the 'left' as the 'right' half of the interval.
I fixed Matlab's random number "seed" using
seed=rng;
followed by
rng(seed);
so it gave the same sequence of 'right' and 'left' each time.
It does 20 iterations, so if everything is linear one expects the final interval to have width about
1e6 / (2^20) \approx 1.
In the last two runs (L=1e4 and L=1e6) this is roughly the case. For the smaller values of L, the top end of the interval is logarithmically collapsed so one immediately gets to much smaller values of a and b; with L=1 the final [a,b] only has width around 0.12.
This algorithm doesn't handle *actually infinite* endpoints, but I think that's a minor snag. When I took [a,b]=[0,REALMAX], and L=1, and 20 iterations, then (I altered the %f format to %g)
starting with a= 0 b= 1.79769e+308
with probLR=0.0 it ended with a= 0 b= 0.000677563
with probLR=0.1 it ended with a= 1.87788 b= 1.87932
with probLR=0.5 it ended with a= 5.67225e+207 b= 5.67609e+207
So this "median" is capable of getting reasonable-size intervals from humungous ones after a modest number of bisections.
I tried it with intervals around 0 such as [-1e5,+1e6] and it still gave civilized-looking results.
Baker, Arnold, Nate, does this offer anything of use to you?
John Pryce
%-----------------------------------------
>> rng(seed); Tfmedian(0, 1e6, 1, 0.5, 20)
a= 0.000000 b=1000000.000000
right, a= 707.106428 b=1000000.000000
left , a= 707.106428 b= 26591.479475
right, a= 4336.244339 b= 26591.479475
left , a= 4336.244339 b= 10738.116846
right, a= 6823.715894 b= 10738.116846
right, a= 8560.015108 b= 10738.116846
left , a= 8560.015108 b= 9587.410623
left , a= 8560.015108 b= 9059.159993
right, a= 8806.051692 b= 9059.159993
left , a= 8806.051692 b= 8931.709310
left , a= 8806.051692 b= 8868.657953
right, a= 8837.299382 b= 8868.657953
right, a= 8852.964783 b= 8868.657953
right, a= 8860.807894 b= 8868.657953
right, a= 8864.732054 b= 8868.657953
left , a= 8864.732054 b= 8866.694786
left , a= 8864.732054 b= 8865.713366
left , a= 8864.732054 b= 8865.222696
left , a= 8864.732054 b= 8864.977372
left , a= 8864.732054 b= 8864.854712
>> rng(seed); Tfmedian(0, 1e6, 1e2, 0.5, 20)
a= 0.000000 b=1000000.000000
right, a= 7070.714267 b=1000000.000000
left , a= 7070.714267 b= 84089.611953
right, a= 24384.391716 b= 84089.611953
left , a= 24384.391716 b= 45282.208242
right, a= 33229.205412 b= 45282.208242
right, a= 38790.360150 b= 45282.208242
left , a= 38790.360150 b= 41910.776968
left , a= 38790.360150 b= 40320.393695
right, a= 39547.978413 b= 40320.393695
left , a= 39547.978413 b= 39932.318495
left , a= 39547.978413 b= 39739.683820
right, a= 39643.715238 b= 39739.683820
right, a= 39691.670524 b= 39739.683820
right, a= 39715.669917 b= 39739.683820
right, a= 39727.675054 b= 39739.683820
left , a= 39727.675054 b= 39733.678983
left , a= 39727.675054 b= 39730.676905
left , a= 39727.675054 b= 39729.175951
left , a= 39727.675054 b= 39728.425495
left , a= 39727.675054 b= 39728.050273
>> rng(seed); Tfmedian(0, 1e6, 1e4, 0.5, 20)
a= 0.000000 b=1000000.000000
right, a= 70358.013003 b=1000000.000000
left , a= 70358.013003 b= 265825.767295
right, a= 136943.916569 b= 265825.767295
left , a= 136943.916569 b= 190826.083718
right, a= 161663.965929 b= 190826.083718
right, a= 175642.786433 b= 190826.083718
left , a= 175642.786433 b= 183077.569644
left , a= 175642.786433 b= 179321.770309
right, a= 177472.775699 b= 179321.770309
left , a= 177472.775699 b= 178394.885009
left , a= 177472.775699 b= 177933.234901
right, a= 177702.856630 b= 177933.234901
right, a= 177818.008574 b= 177933.234901
right, a= 177875.612436 b= 177933.234901
right, a= 177904.421343 b= 177933.234901
left , a= 177904.421343 b= 177918.827540
left , a= 177904.421343 b= 177911.624296
left , a= 177904.421343 b= 177908.022783
left , a= 177904.421343 b= 177906.222054
left , a= 177904.421343 b= 177905.321696
>> rng(seed); Tfmedian(0, 1e6, 1e6, 0.5, 20)
a= 0.000000 b=1000000.000000
right, a= 455089.860562 b=1000000.000000
left , a= 455089.860562 b= 710233.706111
right, a= 579143.462109 b= 710233.706111
left , a= 579143.462109 b= 643711.681410
right, a= 611195.726685 b= 643711.681410
right, a= 627394.209456 b= 643711.681410
left , a= 627394.209456 b= 635537.878902
left , a= 627394.209456 b= 631462.301712
right, a= 629427.322983 b= 631462.301712
left , a= 629427.322983 b= 630444.578820
left , a= 629427.322983 b= 629935.892567
right, a= 629681.593197 b= 629935.892567
right, a= 629808.739237 b= 629935.892567
right, a= 629872.314990 b= 629935.892567
right, a= 629904.103551 b= 629935.892567
left , a= 629904.103551 b= 629919.998002
left , a= 629904.103551 b= 629912.050762
left , a= 629904.103551 b= 629908.077153
left , a= 629904.103551 b= 629906.090351
left , a= 629904.103551 b= 629905.096951
>>