avs devs: plz integrate nicefps() into changefps()/assumefps()

[bond]

changefps/assumefps() allow to input float fps and people make extensively use of this
now the problem is that it doesnt seem to output for eg 23.976 the standard 24000/1001 numerator,denominator but some other high values

this now leads to that for example the x264 encoder is forced to use 64bit precision times, which again causes players like mplayer or quicktime not handling these 64bit, but expecting 32bit, to bork

now we had lots of people reporting problems in the mpeg-4 avc forum reporting these problems and they could be tracked down to the useage of change/assumefps() with float fps input or with input .avi files that have been created from such scripts

now there are three solutions for fixing this:
1) make the whole world use change/assumefps(24000/1001) instead of changefps(23.976) or similar for other framerates
2) make the whole world use the nicefps() filter, as discussed here (http://forum.doom9.org/showthread.php?p=717181#post717181), which scales the framerate in a "nice" way
3) change the behaviour of change/assumefps() to not output these big values anymore by maybe integrating the nicefps()'s function into change/assumefps() or making change/assumefps process the string itself instead of using float math

now i would be really happy if 3) could be done (as 1) and 2) is surely impossible), cause it would remove like "50%" of the x264 error reports ;)

[stickboy]

If only AviSynth used doubles instead of floats, then it more easily could rationalize 23.976 to 2997/125.

Overloading AssumeFPS to take a string might be okay (please, don't add any more *FPS functions), but then you still have the problem of educating people to use it.

[Bidoche]

If only AviSynth used doubles instead of floats, then it more easily could rationalize 23.976 to 2997/125.I don't see how that would help...
Users generally mean 24000/1001 when they put 23.976 and not 2997/125.

Besides FPS is rational, not float or even double, every api with some sense use it like that.
VFW certainly does, avs should do the same (3.0 does)

but then you still have the problem of educating people to use itEasy : add overloaded *FPS functions and change all the old ones to throw a message reporting them deprecated and asking to use the new ones.

[tritical]

If only AviSynth used doubles instead of floats, then it more easily could rationalize 23.976 to 2997/125. I think the main thing is that because it uses floats one has to realize that the precision of the input value is limited to roughly 7 decimal digits. However, that is still enough for values like 23.976 or 29.970. For example, if the current code in assumefps, which is:double n = args[1].AsFloat();
int d = 1;
while (n < 16777216 && d < 16777216) { n*=2; d*=2; }
return new AssumeFPS(args[0].AsClip(), int(n+0.5), d, args[2].AsBool(false), env);were changed to: double n = args[1].AsFloat();
int d = 1;
while (n < 1000000.0 && d < 1000000) { n*=10.0; d*=10; }
int x = int(n+0.5), y = d, t;
while (y) { t = x%y; x = y; y = t; }
return new AssumeFPS(args[0].AsClip(), int(n+0.5)/x, d/x, args[2].AsBool(false), env);then Assumefps(23.976) would result in 2997/125, Assumefps(29.970) would result in 2997/100, Assumefps(119.88) would result in 2997/25, etc... As opposed to what you currently get which is 12570329/524288, 15712911/524288, and 982057/8192. The problem with 30000/1001 or 24000/1001 is that those are repeating decimals and cannot be accurately expressed using a limited precision decimal number. Thus, I don't see any way avisynth could deduce 24000/1001 from a decimal input. To me it seems that any rational fps that requires more than 7 decimal digits of precision (or 15 if it was changed to double) would need to be set using assumefps(numerator,denominator).

[sh0dan]

Can anyone predict problems with the patch above, otherwise it'll go into 2.6.

[stickboy]

I don't see how that would help...
Users generally mean 24000/1001 when they put 23.976 and not 2997/125.Well, a conventional algorithm of repeatedly adding the numerators and denominators of low/high bounds rationalizes 23.976 fine for doubles but not for floats.

And rationalizing to 2997/125 is still an improvement over 12570329/524288 that AviSynth currently generates, yes? Would 2997/125 not address bond's "high-values lead to unnecessary 64-bit computation" issue?Easy : add overloaded *FPS functions and change all the old ones to throw a message reporting them deprecated and asking to use the new ones.Sure, if you want to break backwards compatibility.

[foxyshadis]

The drift between 2997/125 and 24000/1001 is only one-hundredth of a second after three hours. If you never told anyone they'd probably never find out.

[Fizick]

IMO, assumefps(numerator, denominator) is most correct way.
So, if somebody use it explicitly, Avisynth must not change these values.

[Mug Funky]

another possibility is to simply pick the /1001 framerate that fits the input the best.

AFAIK the only rational framerates are those of (colour) NTSC. when someone types 29.97 it is plainly obvious that they mean 30000/1001, so really this number can be assumed without any drawbacks (as stickboy says, who's going to notice 1/100th of a second after 3 hours? considering that 1-frame desync is quite common on DVDs anyway, particularly if they've been standards converted, and nobody seems to notice that).

presets would be interesting too - something like "assumefps("film")" to give 24000/1001, or "assumefps("NTSC") gives 30000/1001, etc. this would certainly be easier to type (and understand...) than 30000/1001 etc.

[Bidoche]

Easy : add overloaded *FPS functions and change all the old ones to throw a message reporting them deprecated and asking to use the new ones.
Sure, if you want to break backwards compatibility.I was answering on how educating users.
That method certainly works

presets would be interesting too - something like "assumefps("film")" to give 24000/1001, or "assumefps("NTSC") gives 30000/1001, etc. this would certainly be easier to type (and understand...) than 30000/1001 etc.Looks interesting

[d'Oursse]

afaik, 24000/1001 is not the fps of the "films". it's the fps used to get the NTSC framerate from a "photographic material produced for the cinema". the framerate of the films is 24 fps (http://www.doom9.org/ivtc-tut.htm). Maybe the word "film" is not correct.

[tritical]

another possibility is to simply pick the /1001 framerate that fits the input the best.

AFAIK the only rational framerates are those of (colour) NTSC. when someone types 29.97 it is plainly obvious that they mean 30000/1001, so really this number can be assumed without any drawbacks (as stickboy says, who's going to notice 1/100th of a second after 3 hours? considering that 1-frame desync is quite common on DVDs anyway, particularly if they've been standards converted, and nobody seems to notice that).
While this would work for getting the 24000/1001 and 30000/1001 ratios, I personally don't think this is a good idea. When someone uses assumefps(23.976) they should, IMHO, get what they asked for. Adding work arounds to have it adjust to another value is just going to add to the confusion when someone really does want 23.976 and not 24000/1001 for whatever reason.

presets would be interesting too - something like "assumefps("film")" to give 24000/1001, or "assumefps("NTSC") gives 30000/1001, etc. this would certainly be easier to type (and understand...) than 30000/1001 etc. Sounds like a good idea.

[bond]

so will my proposal be followed? :)

[tritical]

If anyone is interested in testing, I have merged the code I posted before and Mug Funky's preset idea (though I used the names "ntsc_film", "ntsc_video", "ntsc_double" for 24000/1001, 30000/1001, 60000/1001 respectively) into the changefps/convertfps/assumefps filters in the custom version of avisynth I keep on my website.

[IanB]

Avery's latest blog, Wikipedia and AVI fractions (http://www.virtualdub.org/blog/pivot/entry.php?id=81#body) refers to this article on continued fractions (http://en.wikipedia.org/wiki/Continued_fraction). This might give the narrow minded something to broaden their horizons.

As for guessing what the true FPS the user really intended from a single precision float approximations of FPS, I think I would have to class that with vodoo and other paranomal superstition. Doing so is very fraught. The current code is able to exactly return to the same single precision floating point value originally set, none of the above suggested code mods provide this.

If we change the definition of 29.97 and 23.976 FPS then there will be some lazy users who may be transiently happy but in the long run smart alec hacks, like the proposed, always return to bite you big time. And what do we do with the well intensioned 29.97002997 or 23.976023976 values (which don't fit is a float anyway).

For a case in point consider :- A current user builds a script and set the fps to 23.976 (not 24000/1001), they add an audio track edited in an external editor that has explicit knowledge of single precision 23.976 fps framerate. It works as expected. 9 months later we have a new AVS version, with hacked code, the user is not happy his previous working script inexplicably is now getting audio desync....


The idea for easy to spec string equivalences has merit. Of course it can be implemented immediatly as a simple .avsi script, no need to polute the core.

Bottom line is if you want 30000/1001 fps or 24000/1001 fps then that is what you should spec. So maybe we need to provide text presets to make this easy to understand for the innumerate masses.


P.S. For the uninformed this codewhile (n < 16777216 && d < 16777216) { n*=2; d*=2; }is crudely extracting the mantisa and exponent from the float and storinging them loselessly (well for values less than 2^31) as a rational fraction.

[stickboy]

BTW, would it be useful to modify Info() so that instead of:

Frames per second: 23.9760

it showed:

Frames per second: 23.9760 (24000/1001)

?

[sh0dan]

@stickboy: Info fractions added to CVS.

[Wilbert]

Some discussion on #x264 with respect to this problem

<funmain> bond: high in your opinion is above 23.976 right?
<|bond|> (funmain) bond: high in your opinion is above 23.976 right? <- no
<funmain> |bond|: define 'other high values'
<|bond|> funmain: well it was more meant as a joke that you post there, but it would definitely dont hurt if you would post there
<funmain> 23.976 is based on really really old standards (they should stick to it), i will do bond
<Haali> hehe you seriously propose changing avisynth because of broken qt player?
<|bond|> funmain: 23.976 can be represented as 24000/1001, but thats not 100% correct. avs uses some very high values which make use of 64bit. quicktime doesnt handle that
<|bond|> (Haali) hehe you seriously propose changing avisynth because of broken qt player? <- and mplayer and ffmpeg
<pengvado> we propose to change avisynth because avisynth is _broken_
<pengvado> just because some players happen to play the resulting file doesn't make it correct
<|bond|> (@pengvado) we propose to change avisynth because avisynth is _broken_ <- post your opinion here, cause they dont seem to change it: http://forum.doom9.org/showthread.php?t=104681
<Haali> avisynth is definitely not broken
<|bond|> at least they could add the feature of nicefps()
<|bond|> it wouldnt hurt and help newbies
<Haali> it either passes through what it got from source file or what you input in the script
<Haali> if you do mean 24000/1001 then say so in the script
<|bond|> newbies have no clue about that
<pengvado> except that it doesn't
<pengvado> assumefps(23.976) doesn't set fps=23976/1000
<Haali> because you'd use assumefps(23976,1000) for that, no?
<Haali> anyway, this could be nicely improved by treating the argument as a string, not a double
<pengvado> it seems perfectly reasonable to me to expect assumefps(23.976) and assumefps(23976,1000) to do the same thing
<pengvado> hell, even a double would work. just single precision isn't enough.
<Haali> i agree it can be handled better
<Haali> but in this instance it's the players that can't read valid files, not broken avisynth
<Haali> and pretty obscure players
<Haali> and at least ffmpeg shouldn't be too hard to fix
<funmain> Haali: have u been reading the topic on doom9?
<Haali> yes
<|bond|> some tried to fix ffmpeg to handle 64bit but its still not working correctly and he doesnt answer anymore
<|bond|> noone on the mplayer maillist responded
<Haali> send them some sample they'd definitely want to watch
<|bond|> mplayer ftp isnt working
<Haali> pengvado: btw avisynth uses doubles for args already
<pengvado> I didn't look at the code. but the fps you get from assumefps(23.976) is _exactly_ the float representation on 23.976, not the double representation.
<Haali> yeah, because assumefps only extracts 24 bits from it
<Haali> should have done all 32 :P
<pengvado> ok, so they just need to do the double->rational using nicefps's algo instead of truncating
<Haali> i'd think avoiding a round trip through double can be a better idea
<funmain> pengvado: you dont know.. ?
<pengvado> I know how to fix it, but the patch has already been posted. we just need some avisynth dev to agree to apply it, and I'm not one.
<algern0n> pengvado: time for you to become an avisynth dev then :D
<Koepi> bond is right. you should make an announcement

[tritical]

The current code is able to exactly return to the same single precision floating point value originally set, none of the above suggested code mods provide this. This is definitely not true for all cases... why do you think avisynth currently returns a num/den of 982057/8192 for assumefps(119.88) when the actual binary single precision fp approximation of 119.88 is equal to 15712911/131072? The two reasons it doesn't work for all cases are:

1.) d is limited to < 2^24, which means various values in the range 0 < x < 0.5 (granted it's not a common fps value) will not be translated into a num/den combo that when converted back to float will equal the original. Also, in the current code n only needs to be limited to < 2^23 for the loop condition since single precision floating point only has 23 bits for the mantissa.

2.) It will not work for other various values (119.88 is one example), due to how avisynth's script parser converts to float. Take a look at the floating point part of the Tokenizer::GetNumber() routine, it should be doing all the intermediate stuff in double (otherwise too much error accumulates), but it currently does it in float. For example, if you do assumefps(119.88) avisynth spits out 982057/8192 for a num/den. The 982057/8192 comes from assumefps() calling vi.setfps(num,den) which finds the gcd and and divides it out, in this case it is 32. That means original numbers that get passed are 31425824/262144 while the actual binary fp representation of 119.88 is equal to 31425822/262144. The error comes from the script parser conversion, which, as written, doesn't convert 119.88 to 0x42efc28f (hex value of the 4 bytes at the float memory location), but 0x42efc290. If that routine is changed to use doubles for intermediate steps then the correct value (0x42efc28f) is produced.

Anyways, whether or not the code is changed doesn't really matter to me (that's why I keep a custom version :)).

[bond]

another problem with parsers on such 64bit requiring framerates:
http://forum.doom9.org/showthread.php?t=105154

edit: is the behaviour the same than with assume/changefps when setting the fps via directshowsource?

can we plz change the handling of 29.97, 23.976 aso in avisynth :>

[IanB]

Okay, I reworked fps.cpp in CVS along the lines from Triticals mods. I added a massive stack of presets to seed the idea mill, I don't intended to leave all those options in, I just wanted them written down so we can make a thought out final selection.

I also reworked the number parser, it now uses doubles for the internals.

One approach I experimented with (sorry not in CVS) is bit stuffing from the float to directly pick out the mantissa and exponent and build the rational values directly from there, no surprise here it gives same result as the original *=2 code.

Bottom line is floats just do not have enough precision to accurately represent the exact rational values required. In cases where exactness is required then you really should be specifying the rational values, not a half baked single precision floating point approximation.

Also for the 0<x<0.5 case if it really matters the following can be done to maximise the precission.double d = 1.0/double(args[1].AsFloat());
int n = 1;
while (n < 16777216 && d < 16777216) { n*=2; d*=2; }
return new AssumeFPS(args[0].AsClip(), int(n+0.5), d, ...

[bond]

IanB, will this now change the behaviour avoiding triggering the problems i described in the first post if someone uses changefps(23.976) or assumefps(29.97) aso...?

[Richard Berg]

Aside from code churn, would it break anything if the Avisynth script type 'float' were re-implemented to be a double under the hood?

[raymod2]

I'd like to weigh in on this issue. I don't agree with Tritical's modification. It ignores the real problem which is the (lossy) string to float conversion. It is easy enough to convert directly from the string to the rational representation (losslessly). I have included an algorithm called string_to_frac() which shows how this can be done.

I have also included an algorithm called reduce_frac() which performs the same function as NiceFPS() but much more efficiently. NiceFPS() uses a brute force method that uses floating point math to evaluate every denominator in the interval [1,limit]. reduce_frac() uses continued fractions and best rational approximations to perform the same task using far fewer calculations without using any floating point math.

I am NOT suggesting that reduce_frac() be incorporated into assumefps() as default behavior. It might be useful, however, to add it to the core so that people who want to use it (and accept the resultant loss in accuracy) don't need to download an external plugin.


#include <stdio.h>

typedef unsigned long UINT32;

//
// This function converts a decimal string (ie. "23.976") into a fraction
// (ie. 2997 / 125). By avoiding a round trip through floating point
// representation, this process is lossless.
//
static char string_to_frac(char *str, UINT32 *num, UINT32 *denom)
{
char ch, digits = 0, dp_found = 0;
UINT32 n = 0, d = 1, x, y, t;

while ( (ch = *str++) )
{
if ( ch >= '0' && ch <= '9' )
{
if (++digits > 9) { return(1); } // too many digits
n *= 10; n += (ch - '0');
if (dp_found) { d *= 10; }
}
else if ( ch == '.' )
{
if (dp_found) { return(1); } // more than one decimal point
dp_found = 1;
}
else
{
return(1); // invalid character
}
}

x = (n > d) ? (n) : (d); // set x to the larger of n,d
y = (n > d) ? (d) : (n); // set y to the smaller of n,d

while (y) { t = x%y; x = y; y = t; } // compute the GCD (result in x)

*num = n/x; *denom = d/x;
return(0);
}

//
// This function uses continued fractions to find the best rational
// approximation that satisfies (denominator <= limit). The algorithm
// is from Wikipedia, Continued Fractions.
//
static void reduce_frac(UINT32 *num, UINT32 *denom, UINT32 limit)
{
UINT32 n0 = 0, n1 = 1, n2, nx = *num; // numerators
UINT32 d0 = 1, d1 = 0, d2, dx = *denom; // denominators
UINT32 a2, ax, amin; // integer parts of quotients
UINT32 f1, f2; // fractional parts of quotients
UINT32 i = 0; // number of loop iterations

while (1) // calculate convergents
{
a2 = nx / dx;
f2 = nx % dx;
n2 = n0 + n1 * a2;
d2 = d0 + d1 * a2;

if (f2 == 0) { break; }
if ((i++) && (d2 >= limit)) { break; }

n0 = n1; n1 = n2; d0 = d1; d1 = d2; f1 = f2;
nx = dx; dx = f2;
}

if (d2 <= limit)
{
*num = n2; *denom = d2; // use last convergent
}
else // (d2 > limit)
{
ax = (limit - d0) / d1; // set d2 = limit and solve for a2

if ((a2 % 2 == 0) && (d0 * f1 > f2 * d1))
{
amin = a2 / 2; // passed 1/2 a_k admissibility test
}
else
{
amin = a2 / 2 + 1;
}

if (ax < amin)
{
*num = n1; *denom = d1; // use previous convergent
}
else
{
// calculate best semiconvergent
*num = n0 + n1 * ax;
*denom = d0 + d1 * ax;
}
}
}

int main(int argc, char *argv[])
{
UINT32 n, d;

string_to_frac("29.97003", &n, &d);
reduce_frac(&n, &d, 5000);
printf("%u / %u\n", n, d);
}

[Bidoche]

Isn't it already double, though it calls it float ?

[stickboy]

Nope. AVSValue internally stores a float value. The tokenizer also retrieves floating-point values as floats.

[IanB]

will this now change the behaviour avoiding triggering the problems i described in the first post if someone uses changefps(23.976) or assumefps(29.97)Well correctly parsing the decimal number string into the single precision floating point value should help some. I am still investigating the effect of the *=10 style code versus the original *=2 code.

From my bit stuffing experiments, I better appreciate this statementd is limited to < 2^24, which means various values in the range 0 < x < 0.5Well to get 0.015625 < x < 0.5 to behave better...while (n < 16777216 && d < 0x3FFFFFFF) { n*=2; d*=2; }
would it break anything if the Avisynth script type 'float' were re-implemented to be a double under the hoodProbably every existing plugin that used AVSValue.AsFloat() due to the included (baked in :devil: ) code from avisynth.h

@raymod2, Yep thats the stuff Avery Lee is so excited about ;)

[raymod2]

@AviSynth devs: Have you considered incorporating string_to_frac() into changefps()/assumefps()?

1) It is fast and simple (and uses no floating point math).
2) It allows the user to specify up to 9 digits (previous methods allow 7 or 8).
3) It satisfies IanB's request that the user gets exactly what he specifies.
4) It satisfies bond's original request (common fps choices such as 29.97 and 23.976 result in small dwScale values).

All the other proposed solutions suffer the same flaw: The conversion from string to float adds a small error to the specified value. Any attempt to remove that error will be unreliable since the error is unknown.

[IanB]

@raymod2,

I need to play some more with your routines, but initial thoughts.

To clarify, the string_to_frac() routine effectively always returns NUM as an integer of the string with the "." removed and DENOM as 10**P where P is the number of decimal places. NUM and DENOM then have the GCD stripped out. Thus "29.97"->[2997, 100] and "23.976"->[23976, 1000]->[2997, 125], GCD=8. In fact here the GCD is always going to be (2**A + 5**B) as 2 and 5 are the only prime factors of 10 (and also 10**P). Triticals mods effectively force this in the existing code.

Now the reduce_frac() routine is the interesting bit. Your example "29.97003"->[2997003, 100000]. Then you want to reduce the denominator of this to <=5000. And I seem to get get [60000, 2002], (I must have translated the algo incorrectly, I am away from my C compiler and have to use VB inside Excel, YUCK! More playing at the weekend required)

So okay asuming the code actually produced [30000, 1001] how do we input/choose the "5000" value. This is becoming a little tangled. String presets I can forcibly swallow but I think I might choke if I put a special number string parser into the xxxFPS() routines, it's just to plain hacky.

More thoughts latter,
IanB

[raymod2]

And I seem to get get [60000, 2002], (I must have translated the algo incorrectly, I am away from my C compiler and have to use VB inside Excel, YUCK! More playing at the weekend required)

I compiled the example program using MinGW and it outputs 30000 / 1001 as expected.


So okay asuming the code actually produced [30000, 1001] how do we input/choose the "5000" value. This is becoming a little tangled.

If reduce_frac() were included I would vote for making its use optional (maybe by providing an optional argument to assumefps() that chooses the limit). The user should be the one to make this decision because it introduces error into the originally specified FPS.


String presets I can forcibly swallow but I think I might choke if I put a special number string parser into the xxxFPS() routines, it's just to plain hacky.

A string->float parser already exists. What is hacky about adding a string->ratio parser? It is the right tool for the job and it is very simple.

[IanB]

What is hacky about adding a string->ratio parser? We don't have an AVSValue subtype for ratio, so xxxFPS() exclusively would grow a String parameter that is actually a number. I am not sure it is necessary now I have repaired the string to float routine. --total rubbish deleted--

I am still playing with reduce_frac and other repeated fraction algorithms, be patient.

[stickboy]

What is hacky about adding a string->ratio parser? It is the right tool for the job and it is very simple.If you allow AssumeFPS("29.97"), then you either can't have the preset system proposed earlier or the function needs to decide whether the string argument represents a number or a preset. And sure, it's doable, but I agree it's hacky.
I am not sure it is necessary now I have repaired the string to float routine.So what does AviSynth generate for 23.976 and 29.97 now? If they're reasonable, then I think this is pretty moot.

[raymod2]

@stickboy: I know a hack when I see one and I despise them. A hack is making unnecessary conversions that introduce error. A hack is trying to fix that error with algorithms that work for some values but not others. A hack is making guesses about what your user might have meant. A hack is saying "the error is small and the user probably won't notice if you don't tell him".

[IanB]

@stickboy,

There must be something in the water, I have obviously been halocinating. The error only occasionally effected the very bottom bit of the mantissa, so the net result is no (significant) change.

[mg262]

Ian,

Whatever you end up with, would you overload the relevant SetFPS method in AVISynth.h with SaidFPS(float) so filters have access to the mechanism?

(I guess you've played with replacing { n*=2; d*=2; } with { n*=10; d*=10; } before reduction? That's off the top of my head; hope it makes sense...

Edit: Oops... thiss was already in tritical`s code fragment above...)

[bond]

so did my feature request die slowly or will actually some change be made to the way avisynth currently acts fixing the initial problem?

[IanB]

@bond,

The Named Presets have made it into the 2.5.7 CVS, they just need to be selected, organized and reduced. Triticals mod 10 idea has been parked in the code as a compile option so it won't get forgotten. I have finally tested raymod2's reduce_frac code on a C compiler and I like it, however I am not sure that chosing a denominator limit is the most useful mode of operation, as doing so is really just tantemount to just straight specing the numerator and denominator. Off the top of my head I would expect an epsilon accuracy limit would be more useful, and I also would like to see what Avery does in VDub. There will be some form of continued fraction functionality, I am just still researching the best presentation.

[bond]

ok this means the initial problem will not be solved, as getting people to use the presets is like getting them to set the numerator/denominator. also it would mean to get gui developers to change things

this all will not happen. :(

what about the proposals to solve this from haali and pengvado, wilbert posted?

[IanB]

@Bond,

As to just forcing AssumeFPS(29.97), AVSValue=0x41efc28, to return 2997/100 or 30000/1001 and AssumeFPS(23.976), AVSValue=0x41bfced9, to return 2997/125 or 24000/1001. I have a real problem with doing this, as it would make discontinuities in the number space and materially effect scripts that calculate FPS values near these 2 magic values.

Unfortunatly Triticals mod 10 suggestion and NiceFPS limits the overall precision to a shade less than 20 bits, even adding an extra iteration with an appropriate factor of 2, 4 or 5 still only brings precision back to approx. 22.25 bits.

I am still experimenting with continued fractions as a way to keep both full 24 bit precision and convienient denominator values. The current conversion only uses 24 distinct denominators, i.e 2**n, 0<=n<24 out of a possible 2**24 so there is a lots of hope.

In the meantime to get around the GUI generator restrictions put an .AVSI in your pluggin directory that overloads the AssumeFPS(float) signature.Function AssumeFPS(Clip clip, Float fps) {
# Triticals algorithm (approx)
Return AssumeFPS(clip, Round(fps*1000000.0), 1000000)
}orFunction AssumeFPS(Clip clip, Float fps) {
# Force explicit values
num=(fps == 29.97)?30000:(fps == 23.976)?24000:Round(fps*16777216)
den=(fps == 29.97)?1001:(fps == 23.976)?1001:16777216
Return AssumeFPS(clip, num, den)
}The GCD code in the AssumeFPS(clip, num, den) signature will normalize the final numerator and denominator values.

[raymod2]

As to just forcing AssumeFPS(29.97) to return 2997/100... I have a real problem with doing this

I guess I must be missing something here. Since 29.97 is EXACTLY 2997/100 why would you have a problem with that? When a user specifies 29.97 he should get 29.97, not 29.97 plus the small error introduced by converting it to the 32-bit IEEE floating point representation of 29.97. It is exactly that small error that is causing the large denominators.

[IanB]

I guess I must be missing something here. Since 29.97 is EXACTLY 2997/100...Ding! I can never know the text in the script was exactly 29.97. Inside the code I only ever get to see an AVSValue containing a IEEE single precision float, the value of which is the result the parser turning the text "29.97" into that float. In fact a range of values all result in the same bit pattern for the float representation, as shown in the table belowValue Low High Double Hex
29.97 [ 29.96999836 - 29.97000026 ] = 29.969999313354492, 0x41efc28f
30/1.001 [ 29.97002888 - 29.97003078 ] = 29.970029830932617, 0x41efc29f
23.976 [ 23.97599888 - 23.97600078 ] = 23.975999832153320, 0x41bfced9
24/1.001 [ 23.97602368 - 23.97602558 ] = 23.976024627685547, 0x41bfcee6And I guess this is why you proposed the string input with string_to_frac. However this and the string presets do not address Bond's core problem which he has finaly made me understand. He is using a GUI, it emits a script with the text AssumeFPS(29.97) and he has no hope of getting the Author(s) to mend their ways and emit a more correct text of AssumeFPS(30000, 1001) or AssumeFPS(2997, 100).

Your repeated fraction implementation, reduce_frac, or something similar is probably the ultimate solution, I just need some time to research and experiment with how best to tune it. (remember whatever we do Bond wants exactly AssumeFPS(29.97) to parse nicely.

[Manao]

and he has no hope of getting the Author(s) to mend their ways and emit a more correct text of AssumeFPS(30000, 1001) or AssumeFPS(2997, 100).It's imho a shame. It's up to them to properly emit such functions, especially since _they_ know what the user want.

[stickboy]

However this and the string presets do not address Bond's core problem which he has finaly made me understand. He is using a GUI, it emits a script with the text AssumeFPS(29.97) and he has no hope of getting the Author(s) to mend their ways and emit a more correct text of AssumeFPS(30000, 1001) or AssumeFPS(2997, 100).This seems totally backwards. Why is asking the GUI authors to adjust their output more hopeless than getting AviSynth developers to adjust the parser?

[IanB]

@Manao,

I agree, it is a shame and I am not sure they do actually know. Most people are not mathemagicians and simple don't known the issues about dealing with binary floating point representations and the incompatibilities between base 2 and base 10 numbering systems on the right hand side of the decimal/binary point.

@stickboy,

You are probably right, it is a bit backwards, but fixing it in AVS provides the greatest good. (It's not really the parser, it's the crappy way we currently generate rational FPS from a Float.)

[Manao]

There's no "uncrappy way" to generate fps from a float. That's the whole issue. A float is unprecise, while a fps must be completely precise.

Imho, the best way is to remove the float parameter from those filters ( but i guess a lot of people wouldn't like that ).

[IanB]

:D :D :D



Damn vBulletin lower casing my smilie

[IanB]

Okay, here is a test program I have been exercising for extracting an exact rational pair from a float. The reduce_float routine (hacked from raymod2's code) uses repeated fractions to quickly extract a reasonable rational pair, however it is not always the pair with the smallest denominator. The other routine brute_float is very slow but does find the rational pair with the smallest denominator. The program uses both to cross check.

From inspection, it seems that the smallest denominator for an exact pair is between one half the denominator and the denominator from the reduce_float routine. Any budding mathemagicians got a proof or justification for this, and/or can see a way to get the repeated fraction approach to produce the smallest denominator directly or iteratively faster than brute force.

Personally I am very impressed with the performance of the algorithm and I think it will address Bond's concernes, it produces the expected rational pair for most of the popular fps values, there is just not quite enough precision in a float to correctly reverse 120000/1001 = 119.8801198801, it comes back as 40999/342 = 119.8801169591 a 0.00000243665% error but on the plus side 119.88 does yield 2997/25

For implementation in Avisynth I am undecided whether to just use the repeated fraction algorithm or to supplement it with a range limited brute force to get the absolute smallest denominator. The brute force aproach is very slow try it on a range around 1.0

I await your thoughts, suggestions and comments.

#include <stdlib.h>
#include <stdio.h>

#define UINT32 unsigned long


static void ratio_float(UINT32 *nx, UINT32 *dx, float value)
{
union { float f; UINT32 i; } conv;

if (value < 0) value = -value;

conv.f = value;
*nx = (conv.i & 0x7FFFFF) + 0x800000;
*dx = 0x800000;
int exp = (conv.i >> 23) - 127;
if (exp < 0)
*dx <<= -exp;
else
*dx >>= exp;
}


static bool brute_float(UINT32 lo, UINT32 hi,
UINT32 *num, UINT32 *denom, float value)
{
UINT32 nt, dt;

for (dt=lo; dt<hi; dt++) // Brute force BEST ratio!
{
nt = (UINT32)((double)value * dt); // no rounding

if ((float)((double)nt/(double)dt) == value) // floor
{
*num = nt; *denom = dt;
return true;
}

if ((float)((double)(nt+1)/(double)dt) == value) // ceil
{
*num = nt+1; *denom = dt;
return true;
}
}
*num = nt; *denom = dt;
return false;
}


static void reduce_float(UINT32 *num, UINT32 *denom, float value)
{
UINT32 n0 = 0, n1 = 1, n2, nx; // numerators
UINT32 d0 = 1, d1 = 0, d2, dx; // denominators
UINT32 a2; // integer parts of quotients
UINT32 f2; // fractional parts of quotients

ratio_float(&nx, &dx, value);

for (;;) // calculate convergents
{
a2 = nx / dx;
f2 = nx % dx;
n2 = n0 + n1 * a2;
d2 = d0 + d1 * a2;

if ((f2 == 0) || ((float)((double)n2/(double)d2) == value))
{
*num = n2; *denom = d2; // use convergent
return;
}
n0 = n1; n1 = n2;
d0 = d1; d1 = d2;
nx = dx; dx = f2;
}
}

int main(int argc, char *argv[])
{
int count = 2;
UINT32 n0, d0, n1, d1;

union { float f; UINT32 i; } u;

if (argc > 2) count = atoi(argv[2]);

u.f = 29.97;
if (argc > 1) u.f = atof(argv[1]);
u.i = u.i-count;

for (int i=0;i<=count*2;i++){
reduce_float(&n0, &d0, u.f);

if (brute_float(2, d0/2, &n1, &d1, u.f))
printf("%8u /%7u %.9f (%8u /%7u) 1st Half!\n",
n1, d1, (float)((double)n1/(double)d1), n0, d0);
else if (brute_float(d0/2, d0, &n1, &d1, u.f))
printf("%8u /%7u %.9f (%8u /%7u)\n",
n1, d1, (float)((double)n1/(double)d1), n0, d0);
else
printf("%8u /%7u %.9f\n",
n0, d0, (float)((double)n0/(double)d0));

u.i+=1;
}
}

[squid_80]

Is speed really an issue? Wouldn't the calculation only be done once for a clip?

[mg262]

Ian,

I think you can get the best of both worlds... if you expand the continued fraction expansions for the 2 endpoints of the interval you are interested in (I think you call these lo and hi) until they disagree, I believe that

1) The continued fraction expansion for the optimal result agrees with the above expansions (as far as they agree),

and if we truncate the expansion at this point so that one remaining fraction a/b needs to be found

2) The interval within which a/b is allowed to lie is much larger than the original interval (probably on the order of 1/2)
3) The denominator of the final product is a linear function of a and b (with coefficients that can be calculated)

[2 and 3 together imply that finding a/b by brute force is relatively fast.]

Please take this with a pinch of salt as I don't presently have a chance to check this on paper... I will try and do that soon.

[IanB]

@squid_80,

Well trying to find a rational pair for the float (1.0-epsilon), and then brute forcing for a better pair on my 3GHz PIV takes just on 1 second, on my 400Mhz PII it take over 20 seconds. True, this is one of the worst values, and I can tune and control this, but it pays to be aware.

@mg262,

lo and hi apply to the brute force routine and give it a range to search. In a final version I might use the results of the continued fraction to contrive to scan a much smaller range.

@all,

The routine I am using is not the same as Raymod2's, in his you specify a limit for the denominator and it returns the most accurate rational pair within that constraint. In mine I iteratate for a rational pair that exactly converts back to the original float.