Boost logo

Boost :

Subject: Re: [boost] [preprocessor] Variadics suggestion
From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2012-10-11 07:41:38


On 10/11/2012 2:18 AM, Paul Mensonides wrote:
> And that is the flaw of these algorithms. That behavior doesn't
> scale. What they need to do is take a /relative/ number of steps
> which they can use (not a number of steps left over at the end). The
> exponential algorithms can get enormous numbers of steps extremely
> quickly. The number is actually:

Translating the ASCII-ized garbage...

> /f/(/s/, /?/, /p/, /b/, /?/) = /p/ * (1 - /b/^(/?/ - /s/ - /?/ - 1)) /
> (1 - /b/) - 1

f(s, delta, p, b, omega) = p * (1 - b^(omega - s - delta - 1)) / (1 - b) - 1

omega = LIMIT_EXPR
delta = buffer size

> where /p/ is the number of wrapping bootstraps, /b/ is the exponential
> base used by the algorithm, /?/ is LIMIT_EXPR which is 512 currently,
> and /?/ is the passed buffer size. The /?/ is global, so we have:
>
> /g/(/s/, /?/, /p/, /b/) = /f/(/s/, /?/, /p/, /b/, 512)

g(s, delta, p, b) = f(s, delta, p, b, 512)

> The value of /b/ is algorithm-specific. I believe it is always 2
> (which can be increased fairly easily), but for REPEAT_X, I /know/ it
> is 2. So, for REPEAT_X we have:
>
> /h/(/s/, /?/, /p/) = /g/(/s/, /?/, /p/, 2)

h(s, delta, p) = g(s, delta, p, 2)

> So, in the case above, we have /h/(500, 5, 1) = 62. However, at the
> beginning with no buffer, we'd have /h/(1, 0, 1) which is
>
> 335195198248564927489350624955146153186984145514
> 809834443089036093044100751838674420046857454172
> 585692250796454662151271343847070298664248660841
> 2251521022
>
> The number type that REPEAT_X uses cannot count that high, but the
> arbitrary precision arithmetic mechanism could /in theory/.
>
> Of course, the above is ridiculously high. Assuming infinite memory,
> if you generated one repetition per nanosecond, it would take about 3
> x 10^226 years to complete (if I did the math right).
>
> So, obviously you don't need that many, but the what the algorithm
> should do is uses a relative depth so that the number of available
> steps is not dependent on s. Instead, it would be something like:
>
> /f/(/?/, /p/, /b/) = /p/ * (1 - /b/^(/?/ - 1)) / (1 - /b/) - 1

f(delta, p, b) = p * (1 - b^(delta - 1)) / (1 - b) - 1

Where delta is now the number of backend steps...

> Where /?/ is now the number of backend steps that the algorithm is
> allowed to use. So EXPR(REPEAT_X(10, n, M)) could generate something
> like 510 steps before trampolining without going past s + 10 - 1 in
> the backend. Even something as low as 20 yields unrealistic numbers
> of steps (about 524286).
>
> So, what these algorithms /should/ be are algorithms which allow
> parametric resumption but use either linear multipliers or exponential
> multipliers with relative upper bounds on the backend. The linear
> version would be faster, but the exponential version would yield a
> lost more steps. The current _PARAMETRIC and _X algorithms don't do
> that.
>
> Regards,
> Paul Mensonides
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk