1
$\begingroup$

I have an algorithm with two parameters ($p_1$ and $p_2$) and one result ($x$). Interesting (for me) parameters and results are:

p1   p2     x
2     2     1.998836002
2    16     4.610859226
2   128    13.500098994
2  1024    40.130006757
2  8192   106.270345052
2 65536   259.381852150
3     3     3.992318015
3    24    24.722478220
3   192   207.129843032
3  1536  1509.379356327
3 12288 10150.661621094
4     4     8.319227723
4    32   141.460142017
4   256  3425.946696232
5     5    18.072054640
5    40   856.749884642
6     6    40.715789568
6    48  5200.304026741
7     7    93.505690907
8     8   221.173052610
9     9   527.337735904

How do I find an approximation formula to calculate $x$ from $p_1$ and $p_2$? Please note it doesn't need to be (actually can't be) fully accurate, because $x$ is already an approximation due to the algorithm used:

The algorithm is searching (using brute force) a hash function that can split a set of entries into exactly $n$ subsets of equal size. To do that, it tries to hash each entry of the set using an index. The probability to find an index in one step, that is to split a set into $m$ subsets of equal size $n$, is

$$ p = \frac{(mn)!}{(n!)^m m^{mn}} $$

Or we use the Stirling approximation:

$$ p = \frac{\sqrt{m}}{{(2 \pi n)} ^ \frac{(m - 1)}{2}} $$

This process is repeated until an index is found. The result ($x$) is the number of calls to the universal hash function, which is equivalent to the time it took to find a solution. So I'm trying to estimate how long it will take to split a set.

For the case where $p_1 = p_2$, I do have an approximation formula:

$$ \Big( \frac{-1}{\log{(1-p)}} \Big) ^{1.0457} \frac{3.267}{p_1} $$

$\endgroup$
  • $\begingroup$ You can fit some member of a suitable family of functions to your data. The focus is probably on the asymptotic behaviour. I am not sure if e.g. fitting a 2D polynomial to your data is helpful. $\endgroup$ – mvw Feb 10 '16 at 14:50
  • $\begingroup$ Actually, a 2D polynomial would be good enough for me, but looking at what I found for the p1=p2 case, I guess a good approximation is slightly more complicated. $\endgroup$ – Thomas Mueller Feb 10 '16 at 15:08
  • $\begingroup$ Some crude observations: for $p=2$, $x$ is not far from $\sqrt{2}$, for $p=3$, $x$ and $p2$ are close, for $p1$ $7$,$8$ and $9$, $x$ is about $2^{p2}$. Would linear regression on $p1$, $\log(p2)$ and $log(x)$ make any sense? $\endgroup$ – Jaume Oliver Lafont Feb 13 '16 at 8:19
  • $\begingroup$ @JaumeOliverLafont yes, that works! And then I can do linear regression on $p1$ and the resulting $m$ and $c$ (I think). Thanks a lot! $\endgroup$ – Thomas Mueller Feb 14 '16 at 8:00
  • $\begingroup$ @JaumeOliverLafont thanks to your comment I found an approximation, and have added this as an answer now. Maybe it's possible to simplify the formula, but I wouldn't know how. $\endgroup$ – Thomas Mueller Feb 19 '16 at 13:43
0
$\begingroup$

Using the ideas from Jaume Oliver Lafont (see comment above):

Some crude observations: for $p_1=2$, $x$ is not far from $\sqrt{2}$, for $p_1=3$, $x$ and $p_2$ are close, for $p_1$ 7, 8 and 9, $x$ is about $2^{p_2}$. Would linear regression on $p_1$, $log(p_2)$ and $log(x)$ make any sense?

I analysed how $x$ behaves for $p_1=p_2$. Using the online tool MyCurveFit, I found the approximation $2.37^{p_1-1.4}$. Then I found that $log(p_2)$ and $log(x)$ (if $p_1$ is the same) are related linearly. Again using MyCurveFit, I found the $m$ for that relation is about $0.34+\frac{7}{{p_1}^{2.1}}$.

Finally, I got a formula that I could simplify using Wolfram|Alpha. My approximation is now:

$0.298781 (2.37^{p_1}) (\sqrt[0.34+{p_1}^{2.1}](\frac{p_2}{p_1}))$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Does this really answer your Question? I think it might be better used as additional information in the Question (using the edit link under its tags). $\endgroup$ – hardmath Feb 19 '16 at 12:51
  • $\begingroup$ Yes, it answers the question, but didn't explain how I came up with the answer. I have now added this background information. I'm not saying my answer is the best possible answer, but it should help others that have similar problems. Please note I don't have a mathematical background, and many others also don't. So it's helpful to know what to do (which tools to use) to solve such problems. $\endgroup$ – Thomas Mueller Feb 19 '16 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.