Fibonacci-räknare

[Galgalid]

Jag gorde ett litet program( i python) som låter användaren skriva in ett numer, och fibonacci-talet som motsvarar det numret visas...problemet var at när jag skrev in 1 000 000 så blev det memoryError

Vet ni nåt smidigt sätt att kunna visa större tal...jag vill printa ut det 100 miljonte fibonacci-talet

Här är koden

Kod: Markera allt

#A finonacci-counter
num = input('Enter a number: ')


def fib(num):
    result = [0, 1]
    for i in range(num -2):
        result.append(result[-2] + result[-1])
    global svar
    svar= result[-1]
    return result

fib(num)
print svar 

[gasol]

Det kommer du inte kunna göra... eftersom det är ett så djävla cp stort tal...

Ett tal lagras i datorn i multiplar av bytes.

Hur stora / hur många bytes som ett tal lagras i är olika från språk och platformar, på min 32-bitars dator så finns dessa datatyper i C:

char 1 byte
short  2 bytes
long  4 bytes
long long  8 bytes

(antar att alla är unsigned)
1 byte består av 8 bitar därför kan man i en char lagra max 2^8  = 256 olika tal, dessa är 0 till 255, alltså är maxtalet 255 eller 2^8 -1

för en short så kan man lagra 2^16 - 1 = 65,535

i en long så kan man lagra 2^32 -1 = 4,294,967,295

i en long long så kan man lagra 2^64 = 18,446,744,073,709,551,615

[Galgalid]

jag vet ^^ kan lite c++....hmm...om man skriver resultatet till en fil så borde det ju gå...ska prova det

[Galgalid]

Problemet bottnar i att det lagras i svar innan det skrivs till filen..och svar blir till sist för stor.
Är det möjligt att typ efter att svar är uppe i 300 tecken:
stoppa programet, tömma alla värden utom de 2 senaste, för att sedan fortsätta?

jag är inte så bra så att jag kan sånt än....

[Smygis]

jag kan meddela att det inte har att göra med det gasol snackar om. utan vad som händer är att listorna du skapar har ett hundra miljoner (!) element vardera. och sedan innehåller dem inte direkt små tal. så jag skulle vall gissa på att du behöver en 10 giga byte ram till för att klara den beräkningen ;-) jag använder min mobil för att skriva detta så det kommer se helt stört ut:   

Kod: Markera allt

def fib(fibn): a,b=0,1;for i in xrange(fibn): a,b=b,a+b; return b

nej, jag kan inte göra radbrytningar. return satsen tillhör inte för loopen. sedan borde resten av strukturen inte vara så knepig. min dator har stått och tuggat på det i snart än timme nu :-)

[nicefinger]

Det går .. men du får ordna ett eget tal-lagringssystem. Minns inte nu hur man gör
Det är ett exempel i många programmeringskurser.

[Galgalid]

Jag fixade det

Kod: Markera allt

#A finonacci-counter
num = input('Enter a number: ')


def fib(num):
    result = [0, 1, 1, 2]
    for i in range(num -2):
        result.append(result[-2] + result[-1])
        del result[-3]
    global svar
    svar = result[-1]
    
    f = open(r'/home/galgalid/test.txt', 'w')
    f.write(str(svar))
    f.close()
    return result

fib(num)
print 'Finished!'

Iochmed att talen som inte används raderas hela tiden, blir programet långsammare, men man kan räkna ut större tal

Är det någon som kan visa mig något bra sätt att speeda up det här?

[wellparp]

Hej,

Jag kan inte python så jag ger mig inte på att svara på hur du skall göra där. För att kunna beräkna så stora tal är det snabbast att använda ett så kallat "bignum"-bibliotek. Det snabbaste som finns ute är GNUs gmplib som nås på gmplib.org. Här är ett enkelt program i C som beräknar fibonaccital:

Kod: Markera allt

#include <gmp.h>
#include <stdio.h>

main()
{
  mpz_t f1, f2;

  mpz_init_set_ui (f1, 1);
  mpz_init_set_ui (f2, 1);

  int i;

  for (i = 1; i < 1000000; i++) {
    mpz_add (f1, f1, f2);
    mpz_swap (f1, f2);
  }

  mpz_out_str (0, 10, f2);
  printf("\n");
}

Kom ihåg att även med gmp kommer din beräkning att ta väldigt lång tid! Se till exempel http://www.bigzaphod.org/fibonacci/

[Urban Anjar]

Har för mig att python har long integer med mer eller mindre obegränsad längd, se'n kanske du ändå stöter i taket på något vis, men kolla upp det.

[Galgalid]

Jag räknar ut det 6 miljonte fibonacci-talet nu   är väl färdigt om några timmar -.-'
jag använder mig av mitt föregående kod-exempel.  Vilken datatyp är värdena i en lista som standard?

[Galgalid]

På 1.5 timmar räknade jag ut det 6 000 000 fibonacci-talet:

http://www.speedyshare.com/717438826.html

enjoy   och öppna den i OO  gedit hänger sig xD

EDIT: 253 sidor fullpropade med siffror! OO tar ett tag att läsa in det...började som 7 sidor...37...57.....200....250...253

[per9000]

jag gjorde en liten fibonacci pryl förra sommaren tror jag. Se bilaga.

Output från testprogrammet är

Kod: Markera allt

>python per9000fiblib.py 
Content-Type: text/plain

Test of the Per9000FibLib
author: Per Erik Strandberg, www.pererikstrandberg.se

This Fibonacci Library can work with huge integers
Let us play with 1337^42 = 198389692832016689128025814051186435469808931027259980194805041212767924492279648804437095653839742535006120000819629040274718649969
This integer has has approximately 132 digits.
The largest fibonaccinumber less than 1337^42 is: 126981576631475750014906387931931581692734251880848776469071481399496762848826070039224556421753327196738843828004058553268696153829.

Let us now instead play with 123456789012345678901234567890123
i find that this new integer is enclosed in two fibonacci number as follows:
110560307156090817237632754212345 < 123456789012345678901234567890123 < 178890334785183168257455287891792

Zeckendorf's representation: this integer is composed of the following sum of fibonacci numbers:
F(154) = 110560307156090817237632754212345
F(149) = 9969216677189303386214405760200
F(146) = 2353412818241252672952597492098
F(143) = 555565404224292694404015791808
F(135) = 11825896447871834976429068427
F(133) = 4517090495650391871408712937
F(131) = 1725375039079340637797070384
F(126) = 155576970220531065681649693
F(124) = 59425114757512643212875125
F(118) = 3311648143516982017180081
F(112) = 184551825793033096366333
F(110) = 70492524767089125814114
F(107) = 16641027750620563662096
F(105) = 6356306993006846248183
F(103) = 2427893228399975082453
F(99) = 354224848179261915075
F(95) = 51680708854858323072
F(91) = 7540113804746346429
F(87) = 1100087778366101931
F(83) = 160500643816367088
F(75) = 3416454622906707
F(73) = 1304969544928657
F(69) = 190392490709135
F(67) = 72723460248141
F(61) = 4052739537881
F(59) = 1548008755920
F(55) = 225851433717
F(52) = 53316291173
F(50) = 20365011074
F(46) = 2971215073
F(40) = 165580141
F(37) = 39088169
F(35) = 14930352
F(29) = 832040
F(27) = 317811
F(23) = 46368
F(21) = 17711
F(11) = 144
F(8) = 34
F(3) = 3

A Fibonacci Code representation of this number is thus:
0010000100100000
0000101000101000
0010100100000100
0101001000101000
0010100010100000
0010001000100010
0010001010100101
0000010000010100
0010101000000010
01001000011

Decoding this code gives us: 123456789012345678901234567890123
control:
   123456789012345678901234567890123
 - 123456789012345678901234567890123
------------------------------------
 = 0 (which is nice)

Test of the function isfib(n):
Positive numbers less than 100 that are fib's are:
1 2 3 5 8 13 21 34 55 89
Positive numbers less than 20 that are not fib's are:
4 6 7 9 10 11 12 14 15 16 17 18 19

Som du kan se har den stöd för N'te fibonaccital, fibonaccital större än och mindre än ett annat tal, och Zeckendorf versionen av ett fib-tal ( http://en.wikipedia.org/wiki/Zeckendorf_theorem ).

Betrakta den som licencierad under GPL2+, men jag tror inte det står ngt.

Enjoy,
Per

[per9000]

Det lilla tricket med fibonacci-paret kommer från Wikipedia, för att härleda det rent matematiskt behöver man ett verktyg som kallas Z-transform.

Dessutom har jag fuskat lite och har en lista på det minsta talet som är ett fibonacci-tal för varje tio-potens (precis i början).

Kod-apa? Jo men visst...

/P

[Galgalid]

Wikipedia is your friend