Quibbler, if you do indeed know this guy, you can bust him if he cheats...
I'm still working on the program; I've almost got it down but I gotta run.
Heh,
How would his teacher expect him to do something so complicated? That's completely ridiculous. He doesn't even know what the heck it is in the first place, which I will explain when I finish the program later at home.
Yes you're right teachers can be real bastards. Giving a problem of this difficulty to somebody who would struggle with a "hello world" program is just incomprehensible.
Not only is it a tricky computational problem, but the maths is very awkward. Working out the coeffs of n(n-1)(n-2)... is a project in itself.
Ok, I'm still working on it. Still some problem. Conceptually it's a bit difficult, but easy to implement.
Looking at my code for this program I would say it is both conceptually difficult AND difficult to implement. And I've got pages of hand calculations as well.
I think you have to try the problem by hand and then try to code it at least thats how I approach it. And If I can't do a simple version of the problem by hand I don't understand the maths enough to do the problem then it's time to give up.
Nice challenge pity it was a homework problem.
Done.
From my understanding, the basic setup is you have an array of resulting values from: f(n = 0), f(n = 1), f(n = 2), and so on. But, you don't know the function. You assume it's linear in the form:
Code:
f(n) = sum( value(m)*n^m )
Then you use "Newton's forward difference formula" to figure it out.
Code:
DECLARE FUNCTION linearfunctionValue& (array1() AS INTEGER, n%)
RANDOMIZE TIMER
arraySize% = 5
DIM testarray%(1 TO arraySize%) 'the coefficients, smallest first.
DIM testdiff&(1 TO arraySize%) 'the differences.
DIM testdiffFirst&(1 TO arraySize%) 'the other differences...
'Assume it starts at 1, for sanity's sake.
'create the coefficients and print the thing out.
PRINT
for i% = arraySize% to 1 step -1
testarray%(i%) = INT(RND*10) + 1
if i% <> 1 THEN
newstringtoprint$= STR$(testarray%(i%)) + "n" + "^" + LTRIM$(STR$(i%-1)) + " + "
else
newstringtoprint$= STR$(testarray%(i%))
end if
PRINT newstringtoprint$;
next i%
PRINT
PRINT
'create the differences from the coefficients.
'create the first row.
for i% = 1 to arraySize% + 2
testdiff&(i%) = linearFunctionValue(testarray%(), i%-1)
if i% = 1 then testdiffFirst&(1) = testdiff%(i%)
print testdiff&(i%);
next i%
print
'get the differences from subsequent rows.
for j% = arraySize% + 1 to 2 step -1
for i% = 1 to j% step 1
if i% = 1 then testdiffFirst&(arraySize% - j% + 2) = testdiff&(i%)
testdiff&(i%) = testdiff&(i%+1) - testdiff&(i%)
print testdiff&(i%);
next i%
print
next j%
'Compute the coefficients using Newton's forward difference formula.
'The forward difference formula is given by:
'sum( a(k)*choose(n k) ) from {k = 0 to K = P}, where:
'P is the number of terms in the resulting linear equation. (arraySize%)
'n is the variable in the equation.
'The a(k)'s are the constant terms that we want to find.
DIM value1&(0 TO arraySize%)
DIM value2&(1 TO arraySize%)
'The value2() is the output, which should equal testarray.
print
k% = 1: value2&(1) = testdiffFirst&(1): value1&(1) = 1
for i% = 2 to arraySize%
for j% = i% to 2 step -1
if j% = 2 and i% > 2 then
value1&(j%) = -value1&(j&) * (i% - 2)
else
value1&(j%) = value1&(j% - 1) - value1&(j&) * (i% - 2)
end if
n# = testdiffFirst&(i%) / k%
value2&(j%) = value2&(j%) + value1&(j%) * n#
next j%
k% = k% * i%
next i%
print
for i% = 1 to arraySize%
print value2&(i%);
next i%
sleep
SYSTEM
FUNCTION linearfunctionValue& (array1() AS INTEGER, n%)
'Assume array1(1) is the start; i.e. the exponent is 0.
maxarray1% = UBOUND(array1)
for i% = 1 to maxarray1%
total1& = total1& + array1(maxarray1%-i%+1)*n%^(maxarray1%-i%)
next i%
linearfunctionValue& = total1&
END FUNCTION
What am I doing wrong when I run your program I get
Subscript out of range (I put it up to 50) ...Then
Overflow.
Try mine I've used the data from the link in a data statement.
Code:
CLS
DATA 1,19,143,607,1789,4211,8539
'DATA 5,0,1,20,69,160,305
n = 7
DIM h(10, 10)
FOR i = 1 TO n
READ y(i)
NEXT i
z(1) = y(1)
FOR m = n - 1 TO 1 STEP -1
k = k + 1
diff(k) = z(1)
FOR i = 1 TO m
z(i) = y(i + 1) - y(i)
NEXT i
FOR i2 = 1 TO m
y(i2) = z(i2)
NEXT i2
NEXT m
k = 1
FOR i = 1 TO n
IF i > 2 THEN k = k * (i - 1)
diff(i) = diff(i) / k
IF diff(i) = 0 THEN 10
NEXT i
10 f(1) = 1
FOR j2 = 1 TO i - 3
FOR j1 = 1 TO j2
ff(j1) = ABS(f(j1)) * j2 + ABS(f(j1 + 1))
NEXT j1
FOR j1 = 1 TO j2 + 1
IF j1 MOD 2 = 0 THEN f(j1 + 1) = ff(j1) ELSE f(j1 + 1) = -ff(j1)
h(j2, j1) = f(j1)
NEXT j1
NEXT j2
FOR i8 = 1 TO i
h(0, i8) = 1
NEXT i8
coeff(1) = diff(1)
kk = 1
FOR i8 = 0 TO i - 3
FOR i7 = 1 TO i - 2
x1 = x1 + diff(i7 + 1 + i8) * h(i7 - 1 + i8, i7)
NEXT i7
kk = kk + 1
coeff(kk) = x1
x1 = 0
NEXT i8
FOR g = 1 TO kk
PRINT coeff(g); "x^"; g - 1
NEXT g
If you use more than about 5-6 coefficients, your numbers will quickly get larger than 64 bits.