Partition function P: Difference between revisions
Content added Content deleted
(Partition function P en FreeBASIC) |
m (→{{header|FreeBASIC}}: fix then integer version and added then big number version) |
||
Line 350: | Line 350: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
===Unsiged 64bit version=== |
|||
{{trans|Python}} |
{{trans|Python}} |
||
<lang freebasic> |
<lang freebasic>Function PartitionsP(n As UInteger) As ULongInt |
||
' if n > 416, the result becomes to large for a unsigned 64bit integer |
|||
⚫ | |||
Dim As |
Dim As ULongInt p(n) |
||
Dim As UInteger k, j |
|||
p(0) = 1 |
p(0) = 1 |
||
For i As |
For i As UInteger = 1 To n |
||
k = 0 |
k = 0 |
||
While |
While TRUE |
||
k += 1 |
k += 1 |
||
j = (k * (3*k - 1)) \ 2 |
j = (k * (3*k - 1)) \ 2 |
||
Line 366: | Line 369: | ||
p(i) -= p(i - j) |
p(i) -= p(i - j) |
||
End If |
End If |
||
j = (k * (3*k + 1)) \ 2 |
'j = (k * (3*k + 1)) \ 2 |
||
j += k |
|||
If (j > i) Then Exit While |
If (j > i) Then Exit While |
||
If (k And 1) Then |
If (k And 1) Then |
||
p(i) += p(i - j) |
p(i) += p(i - j) |
||
Else |
Else |
||
Line 379: | Line 383: | ||
Print !"\nPartitionsP: "; |
Print !"\nPartitionsP: "; |
||
For x As |
For x As UInteger = 0 To 12 |
||
Print PartitionsP(x);" "; |
|||
Next x |
Next x |
||
⚫ | |||
⚫ | |||
Print !"\n\ndone" |
|||
Sleep</lang> |
|||
{{out}} |
|||
<pre>PartitionsP: 1 1 2 3 5 7 11 15 22 30 42 56 77</pre> |
|||
===Big numbers version=== |
|||
{{libheader|GMP}} |
|||
[https://rosettacode.org/wiki/9_billion_names_of_God_the_integer#FreeBASIC From the 9_billion_names_of_God_the_integer entry] |
|||
<lang freebasic>' version 26-06-2021 |
|||
' compile with: fbc -s console |
|||
#Include Once "gmp.bi" |
|||
⚫ | |||
' based on Numericana code example |
|||
Dim As ULong a, b, i, k |
|||
Dim As Long j |
|||
Dim As Mpz_ptr s = Allocate(Len(__mpz_struct)) : Mpz_init(s) |
|||
Mpz_set_ui(p(0), 1) |
|||
For i = 1 To max |
|||
j = 1 : k = 1 : b = 2 : a = 5 |
|||
While j > 0 |
|||
' j = i - (3*k*k+k) \ 2 |
|||
j = i - b : b = b + a : a = a + 3 |
|||
If j >= 0 Then |
|||
If k And 1 Then Mpz_add(s, s, p(j)) Else Mpz_sub(s, s, p(j)) |
|||
End If |
|||
j = j + k |
|||
If j >= 0 Then |
|||
If k And 1 Then Mpz_add(s, s, p(j)) Else Mpz_sub(s, s, p(j)) |
|||
End If |
|||
k = k +1 |
|||
Wend |
|||
Mpz_swap(p(i), s) |
|||
Next |
|||
Mpz_clear(s) |
|||
End Sub |
|||
' ------=< MAIN >=------ |
|||
#Define max 6666 |
|||
Dim As UInteger n |
|||
Dim As ZString Ptr ans |
|||
Dim As Double t = Timer |
|||
ReDim big_p(max) As Mpz_ptr |
|||
For n = 0 To max |
|||
big_p(n) = Allocate(Len(__mpz_struct)) : Mpz_init(big_p(n)) |
|||
Next |
|||
PartitionsP(max, big_p()) |
|||
ans = Mpz_get_str (0, 10, big_p(max)) |
|||
Print "PartitionsP("; Str(max); ") = "; " "; *ans |
|||
For n = 0 To max |
|||
Mpz_clear(big_p(n)) |
|||
Next |
|||
Print Using "time = ###.## ms"; (Timer - t) * 1000 |
|||
' empty keyboard buffer |
|||
While InKey <> "" : Wend |
|||
Print : Print "hit any key to end program" |
|||
⚫ | |||
⚫ | |||
{{out}} |
|||
<pre>PartitionsP(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863 |
|||
time = 32.97 ms</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |