Qbasicnews.com
January 26, 2020, 08:55:42 AM
 Welcome, Guest. Please login or register. 1 Hour 1 Day 1 Week 1 Month Forever Login with username, password and session length
 Home Help Search Login Register
 Pages: 1 [2]
 Author Topic: challenge finite difference  (Read 10742 times)
Quibbler
New Member

Posts: 17

 « Reply #15 on: November 10, 2005, 04:21:23 PM »

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.
 Logged
Agamemnus
x/ \z

Posts: 3491

 « Reply #16 on: November 11, 2005, 10:06:55 PM »

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
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Agamemnus
x/ \z

Posts: 3491

 « Reply #17 on: November 13, 2005, 12:44:25 PM »

What, no prize? :\
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Quibbler
New Member

Posts: 17

 « Reply #18 on: November 14, 2005, 08:44:44 AM »

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
 Logged
Agamemnus
x/ \z

Posts: 3491

 « Reply #19 on: November 14, 2005, 03:17:35 PM »

If you use more than about 5-6 coefficients, your numbers will quickly get larger than 64 bits.
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Quibbler
New Member

Posts: 17

 « Reply #20 on: November 16, 2005, 09:26:04 AM »

Don't know what you mean. The only things that will overflow are the matrix and the arrays when they get over 10 elements - which is easily dealt with. At least it works!
 Logged
Agamemnus
x/ \z

Posts: 3491

 « Reply #21 on: November 16, 2005, 01:16:47 PM »

6^9 is a large number.
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
 Pages: 1 [2]
Jump to: