Ooops
November 28, 2020, 02:47:19 PM

Author Topic: [bb] mathematical algorithms by 5t@nKy [ 1+ years ago ]  (Read 395 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bb] mathematical algorithms by 5t@nKy [ 1+ years ago ]
« on: June 29, 2017, 12:28:41 AM »
Title : mathematical algorithms
Author : 5t@nKy
Posted : 1+ years ago

Description : some mathematical algorithms

Code :
Code: BlitzBasic
  1. Here are some of my collections:
  2.  
  3. this is the 'heron-algorithm' with which you can get the square root from 'n'
  4.  
  5. Function Sqr#(n#)
  6.    x0#=1
  7.    repeat
  8.       check#=0.5*(x0#+n#/x0#)
  9.       x0#=x1#
  10.    until check#=x0#
  11.    return x0#
  12. end function
  13.  
  14. this function is to get the greatest common divisor:
  15.  
  16. Function gcd(A,B)
  17.    While B > 0
  18.       R=A mod B
  19.       A=B
  20.       B=R
  21.    Wend
  22.    Return A
  23. End Function
  24.  
  25. this function is to get the least common denominator and based on the gcd function
  26.  
  27. Function lcd(A,B)
  28.    C=(A*B)/gcd(A,B)
  29.    Return C
  30. End Function
  31.  
  32. to get the factorial of a number you can use this
  33.  
  34. Function fac(n)
  35.    check=1
  36.    For i=1 To n
  37.       check=check*1
  38.    Next
  39.    Return check
  40. Emd Function
  41.  
  42. this function is to get the binomial coefficient, this is to get the number of Pascal's triangle (n choose k)
  43.  
  44. Function nCk(n,k)
  45.    Return Fac(n)/(Fac(k)*Fac(n-k))
  46. End Function
  47.  
  48. so that's it!
  49.  
  50. I hope it's useful and sorry for my bad english^^


Comments :


Matty(Posted 1+ years ago)

 Without actually testing it myself I would make the comment that with Heron's Algorithm it would be better to finish the repeat..until loop when abs(check-xo)<some small tolerance value as otherwise it could loop indefinitely for some values.


Floyd(Posted 1+ years ago)

 Sometimes you have to be careful with integer arithmetic as well.With large numbers A*B can 'overflow'. Here is an example of the problem and a corrected lcd().
Code: [Select]
big1 = 100000
big2 = 150000

Print gcd(big1, big2)
Print lcd(big1, big2)
Print lcd2(big1, big2)

WaitKey

Function gcd(A,B)
   While B > 0
      R=A Mod B
      A=B
      B=R
   Wend
   Return A
End Function

Function lcd(A,B)
   C=(A*B)/gcd(A,B)
   Return C
End Function

Function lcd2(A,B)
   Return A * ( B / gcd(A,B) )
End Function



TAS(Posted 1+ years ago)

 Function fac(n)   check=1   For i=1 To n      check=check*1   Next   Return checkEmd Function;should beFunction fac(n)   check=1   For i=1 To n      check=check*n   Next   Return checkEnd Function


degac(Posted 1+ years ago)

 I think there's a type-error in the FAC function
Code: [Select]
Function fac(n)
   check=1
   For i=1 To n
      check=check*i
   Next
   Return check
End Function

Print "4! = "+fac(4)
Print "3! = "+fac(3)
Print "-1! = "+fac(-1)
Print "-4! = "+fac(-4)

Print "0! = "+fac(0)



Warpy(Posted 1+ years ago)

 That works for me... factorial isn't really defined for negative numbers.


_PJ_(Posted 1+ years ago)

 Lots of bugs in the original code. Some of it wont even compile, for example: "Emd Function"Anyway, here's some fixed and optimised versions:
Code: [Select]
Function Fac%(n%)
If(Not(n%))Then Return 0
Local nReturn%=1
Local nIter%=1
For nIter%=1 To n%
nReturn%=nReturn%*nIter%
Next
Return nReturn%
End Function

Function nCk%(n%,k%)
If (k%>0) And (k<n%) Then Return Fac(n%)/(Fac(k%)*Fac(n-k%))
Return 0
End Function

Function Gcd%(A%,B%)
Local n%=0
If (B%<1) Then Return 0
While (B%)
n=A% Mod B%
A%=B%
B%=n%
Wend
Return A%
End Function
I'm not sure what "your" Heron's algorithm is trying to do, but as it stands, it doesn't even follow Heron's formula or stops itself from looping to infinity. You have thrown in values like x1# for no reason whatsoever. Thus it fails on pretty much everything.Recommend using Heron's ACTUAL algorithm:fCurrent#=0.5*(fLast#+(n%/fLast#))Using this formula limited by n iterations (It should never need that many, but makes a good prevention of infinite loops) gives a pretty good return.Dunnno whether it's faster or slwoer than Blitz' default Sqr() or even, whether or not it gives as good accuracy.
Code: [Select]
Function Sqrt#(n%)
Local fCurrent#=n%
Local fLast#=0.5*(fCurrent#+(n%/fCurrent#))
Local nIter%=1
While ((nIter)*(nIter%<n))
nIter%=nIter%+1
fCurrent#=0.5*(fLast#+(n%/fLast#))
fLast#=fCurrent#
Wend
Return fLast
End Function
Note for future reference: Test your code a bit before submitting it ;)


Floyd(Posted 1+ years ago)

 This all needs to be done more carefully.First a minor fix, Fac(0) should return 1. That is by definition.As with the lcd function the intermediate calculations can easily overflow even if the final result is reasonably small. For example, nCk( n, 2 ) should always be n*(n-1)/2. Thus nCk( 21, 2 ) is 21*20/2 = 210. There is no reason to fool around with huge numbers like Fac(21)/Fac(19) just to get 21*20.Also notice the symmetry with nCk( n, k ) = nCk( n, n - k ). We don't need to calculate nCk( 21, 19 ) directly because we know it is the same as nCk( 21, 2 ).Anyhow, here's the right way to calculate nCk, which I have renamed nCr to match the way it is usually named on scientific calculators. Note for example that nCr( 21, 2 ) returns 210 as it should.The original nCk( 21, 2 ) manages to produce -5.
Code: [Select]
Function nCr( n, r )  ; binomial coefficient "n choose r"
If r > n/2 Then Return nCr( n, n - r )
c = 1
For d = 1 To r
c = ( c * ( n +1 - d ) ) / d
Next
Return c
End Function



_PJ_(Posted 1+ years ago)

 Thanks, Floyd. [/i]

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal