0
$\begingroup$

Given the following inputs and outputs to a function, how would I determine an algorithm to fit?

f( 1 ) = 1
f( 2 ) = 2
f( 3 ) = 3
f( 4 ) = 2
f( 5 ) = 4
f( 6 ) = 6
f( 7 ) = 3
f( 8 ) = 4
f( 9 ) = 14
f( 10 ) = 9
f( 11 ) = 18
f( 12 ) = 12
f( 13 ) = 12
f( 14 ) = 42
f( 15 ) = 15
f( 16 ) = 4
f( 17 ) = 24
f( 18 ) = 40
f( 19 ) = 60
f( 20 ) = 51
f( 21 ) = 24
f( 22 ) = 30
f( 23 ) = 130
f( 24 ) = 90
f( 25 ) = 60
f( 26 ) = 72
f( 27 ) = 140
f( 28 ) = 42
f( 29 ) = 156
f( 30 ) = 48
f( 31 ) = 15
f( 32 ) = 12
f( 33 ) = 168
f( 34 ) = 48
f( 35 ) = 414
f( 36 ) = 483
f( 37 ) = 33
f( 38 ) = 36
f( 39 ) = 660
f( 40 ) = 39
f( 41 ) = 380
f( 42 ) = 672
f( 43 ) = 437
f( 44 ) = 364
f( 45 ) = 403
f( 46 ) = 315
f( 47 ) = 550
f( 48 ) = 48
f( 49 ) = 48
f( 50 ) = 369
f( 51 ) = 1950
f( 52 ) = 481
f( 53 ) = 280
f( 54 ) = 180
f( 55 ) = 90
f( 56 ) = 56
f( 57 ) = 144
f( 58 ) = 756
f( 59 ) = 252
f( 60 ) = 4278
f( 61 ) = 4350
f( 62 ) = 816
f( 63 ) = 105
f( 64 ) = 12
f( 65 ) = 432
f( 66 ) = 98
f( 67 ) = 120
f( 68 ) = 1924
f( 69 ) = 186
f( 70 ) = 64
f( 71 ) = 8736
f( 72 ) = 4004
f( 73 ) = 351
f( 74 ) = 552
f( 75 ) = 32604
f( 76 ) = 720
f( 77 ) = 77
f( 78 ) = 496
f( 79 ) = 16740
f( 80 ) = 6783
f( 81 ) = 130
f( 82 ) = 72
f( 83 ) = 1680
f( 84 ) = 330
f( 85 ) = 228
f( 86 ) = 152
f( 87 ) = 87
f( 88 ) = 240
f( 89 ) = 711
f( 90 ) = 6930
f( 91 ) = 1344
f( 92 ) = 1947
f( 93 ) = 495
f( 94 ) = 1680
f( 95 ) = 30240
f( 96 ) = 96
f( 97 ) = 25200
f( 98 ) = 24486
f( 99 ) = 22440
f( 100 ) = 540
f( 101 ) = 1566
f( 102 ) = 279
f( 103 ) = 24024
f( 104 ) = 5040
f( 105 ) = 1197
f( 106 ) = 336
f( 107 ) = 48450
f( 108 ) = 707
f( 109 ) = 153972
f( 110 ) = 3009
f( 111 ) = 1958
f( 112 ) = 3068
f( 113 ) = 2366298
f( 114 ) = 37240
f( 115 ) = 5628
f( 116 ) = 1674
f( 117 ) = 4635
f( 118 ) = 34099
f( 119 ) = 40194
f( 120 ) = 48300
f( 121 ) = 43680
f( 122 ) = 13992
f( 123 ) = 2568
f( 124 ) = 4368
f( 125 ) = 234
f( 126 ) = 1680
f( 127 ) = 105
f( 128 ) = 24
f( 129 ) = 5320
f( 130 ) = 4664
f( 131 ) = 8760
f( 132 ) = 145860
f( 133 ) = 1361122
f( 134 ) = 630
f( 135 ) = 12078
f( 136 ) = 135
f( 137 ) = 17160
f( 138 ) = 445536
f( 139 ) = 6612
f( 140 ) = 15960
f( 141 ) = 99540
f( 142 ) = 34632
f( 143 ) = 14430
f( 144 ) = 57810
f( 145 ) = 39240
f( 146 ) = 24252
f( 147 ) = 1008
f( 148 ) = 144
f( 149 ) = 54054
f( 150 ) = 171380
f( 151 ) = 3444
f( 152 ) = 37076
f( 153 ) = 1320
f( 154 ) = 1188810
f( 155 ) = 3013
f( 156 ) = 91560
f( 157 ) = 239666
f( 158 ) = 720720
f( 159 ) = 11589240
f( 160 ) = 1260
f( 161 ) = 264040
f( 162 ) = 294
f( 163 ) = 1740
f( 164 ) = 16170
f( 165 ) = 67284
f( 166 ) = 162
f( 167 ) = 1560
f( 168 ) = 9798
f( 169 ) = 74542
f( 170 ) = 62118
f( 171 ) = 508164
f( 172 ) = 578952
f( 173 ) = 156
f( 174 ) = 85470
f( 175 ) = 636
f( 176 ) = 2880
f( 177 ) = 6120
f( 178 ) = 1890
f( 179 ) = 98640
f( 180 ) = 329448
f( 181 ) = 1452990
f( 182 ) = 39480
f( 183 ) = 1833
f( 184 ) = 43000
f( 185 ) = 28210
f( 186 ) = 51414
f( 187 ) = 1358708
f( 188 ) = 4218
f( 189 ) = 83754
f( 190 ) = 146160
f( 191 ) = 9090
f( 192 ) = 870
f( 193 ) = 340
f( 194 ) = 168
f( 195 ) = 1979040
f( 196 ) = 251940
f( 197 ) = 168
f( 198 ) = 6020
f( 199 ) = 28200
f( 200 ) = 9006
f( 201 ) = 388
f( 202 ) = 3817632
f( 203 ) = 9975
f( 204 ) = 360
f( 205 ) = 35784
f( 206 ) = 9490
f( 207 ) = 1260
f( 208 ) = 138
f( 209 ) = 1911
f( 210 ) = 337554
f( 211 ) = 166152
f( 212 ) = 375648
f( 213 ) = 7182
f( 214 ) = 81788
f( 215 ) = 2604
f( 216 ) = 40455
f( 217 ) = 42432
f( 218 ) = 1115180
f( 219 ) = 406980
f( 220 ) = 85680
f( 221 ) = 8484
f( 222 ) = 10440
f( 223 ) = 5910
f( 224 ) = 12390
f( 225 ) = 224
f( 226 ) = 2520
f( 227 ) = 420420
f( 228 ) = 159120
f( 229 ) = 27192
f( 230 ) = 128520
f( 231 ) = 15660
f( 232 ) = 2772
f( 233 ) = 13095
f( 234 ) = 286440
f( 235 ) = 1789320
f( 236 ) = 175140
f( 237 ) = 8810490
f( 238 ) = 185650
f( 239 ) = 78672
f( 240 ) = 2055648
f( 241 ) = 3480
f( 242 ) = 27612420
f( 243 ) = 990
f( 244 ) = 21240
f( 245 ) = 769860
f( 246 ) = 4140
f( 247 ) = 63756
f( 248 ) = 28890
f( 249 ) = 3420
f( 250 ) = 11704
f( 251 ) = 1014600
f( 252 ) = 16560
f( 253 ) = 1226160
f( 254 ) = 55440
f( 255 ) = 315
f( 256 ) = 24

It's been a while since I've had to do it, but I recall a process for building polynomial functions based on input & output. I would appreciate help in remembering the process, and I would also be interested to know if there are any tools to help.

$\endgroup$
  • 1
    $\begingroup$ Even though this is not homework, you should provide us with what you have so it becomes easier for people to understand your level and also allows them to answer the question well so you can understand it. $\endgroup$ – Jeel Shah Mar 2 '13 at 6:33
  • $\begingroup$ You can always create a discrete function. Like this: $$f(x) = \matrix{1 & & ; x = 1\\2 & & ; x = 2\\ \vdots}$$ $\endgroup$ – hjpotter92 Mar 2 '13 at 6:38
  • 1
    $\begingroup$ Look up interpolation and curve fitting. $\endgroup$ – Daryl Mar 2 '13 at 6:42
  • $\begingroup$ Interpolation might be what I was remembering from college, but I'm not sure it's actually what I need. It seems to be more for calculating missing data in-between existing data points. I'm looking into GNU Octive as a possible tool to help me solve this. $\endgroup$ – Anthony F Mar 2 '13 at 7:51
  • $\begingroup$ Is there any context for the data. Curve fitting usually relies on understanding the physics behind the data otherwise there are just too many things you can do with a data. It is always possible to fit order n-1 polynomial to a sample with n data points, but I don't think that's what you want. $\endgroup$ – mythealias Jul 23 '13 at 2:46
2
$\begingroup$

The first step is to look at the simple $XY$ plot of the data:

plot1

Whoa. What if we take the logarithm of $Y$?

logplot

This looks like a power of $X$ with a lot of noise. Averaging the ratio of $\ln\ln Y/\ln X$ gives $0.42$. Indeed, $\ln Y\approx X^{0.42}$ is a reasonable "smoothed" approximation.

power

But I don't think that curve-fitting is the way to go here. The nature of the function, and the fact that the argument runs from $1$ to $256$ suggest that some binary operations might be involved. And look, we have spikes at

113 = 0b01110001
159 = 0b10011111
242 = 0b11110010

Actually, I suspect we should subtract $1$ from $X$ to make it run from $0$ to $255$. Then these three spikes are at

112 = 0b01110000
158 = 0b10011110
241 = 0b11110001 

Must be something about these chains of 0s and 1s.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

The algorithm that you remember may be this, but I doubt if it is going to perform well on this data...

Consider the polynomial $\mathrm{shriek}(x) = (x-1)(x-2)(x-3) \cdots (x-256)$ and define the family of polynomials $g_i(x) = \frac{\mathrm{shriek}(x)}{x-i}$ for $i = 1, \ldots, 256$. $\mathrm{Shriek}(x)$ has $256$ terms and $(x-i)$ is one of them for every value of $i$ from $1$ to $256$ so $g_i(x)$ has $255$ terms.

$g_i(x)$ has the useful property that $g_i(x)$ is zero for every value of $x$ in $[1, 256]$ except $x=i$ and $g_i(i)$ is non-zero. In fact, it is a very large number.

For this reason, it's sensible to further define $h_i(x) = \frac{g_i(x)}{g_i(i)}$ so that $h_i(x)$ is now $0$ everywhere in $[1,256]$ except at $x=i$ and $h_i(i)$ is $1$.

We can now use this useful basis to construct a polynomial that fits your function $f(x)$...

$$F(x) = \sum_{i = 1}^{256} (f(i) h_i(x))$$

As others have pointed out, there is a great deal of structure in your data and the polynomial $F(x)$ may not simplify to something succinct that captures the structure.

Codicil

I tried it with Mathematica on my Raspberry Pi ...

f[ 1 ] = 1; f[ 2 ] = 2; f[ 3 ] = 3; f[ 4 ] = 2; f[ 5 ] = 4; f[ 6 ] = 6; f[ 7 ] = 3; f[ 8 ] = 4
f[ 9 ] = 14; f[ 10 ] = 9; f[ 11 ] = 18; f[ 12 ] = 12; f[ 13 ] = 12; f[ 14 ] = 42; f[ 15 ] = 15; f[ 16 ] = 4
...
f[ 249 ] = 3420; f[ 250 ] = 11704; f[ 251 ] = 1014600; f[ 252 ] = 16560; f[ 253 ] = 1226160; f[ 254 ] = 55440; f[ 255 ] = 315; f[ 256 ] = 24; 

g[i_,x_] := Product[ If[i==j,1,(x-j)],{j,256}]

h[i_,x_] := g[i,x]/g[i,i]

F[x_] := Sum[ f[i] h[i,x], {i,256} ]

Simplify[F[x]]

Unsurprisingly, it produces something horrendous

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Welcome to math.SX! Read here about writing mathematics. $\endgroup$ – Smylic Mar 20 '17 at 15:51

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.