Desempenho em Sequencia de Fibonacci

Olá, estou desenvolvendo um programa de fibonacci, para aprender na pratica um pouco sobre desempenho, e estou tentando desenvolver um que alcançe numeros cada vez maiores. Primeiro usei um metodo recursivo, que achei no java como programar, so que so depois de 50 começava a dar erro de StackOverFlow.
Então resolvi quardar os resultados em um array, dai consegui chegar ate 1000.
Depois resolvi fazer o programa calcular todos, do 0 até o numero escolhido, para acabar com o StackOverFlow. O Programa chegou ate 10.000.
Depois disso ví que o problema não era processamento, e sim muita coisa na memoria. Resolvi que a cada vez que o fibonacci achava mais um numero, deveria apagar o bigInteger que ficava dois atrás, que não seria mais util.

Apos saber fibonacci 5, pode se apagar fiboancci 3, já que o 6, so vai ter que saber quanto é o 4 + o 5. Isso ajudou e agora o programa pode calcular qualquer resultado, o que as vezes pode demorar. Vou postar o codigo

import java.util.Scanner;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.math.BigInteger;

public class FibonacciSequence
{
  public static BigInteger fibonacci( int n )
  {
    BigInteger[] sequence;
    sequence = new BigInteger[n + 1];
    
    for ( int c = 0 ; c < n + 1 ; ++c )
    {
      if ( c == 0 || c == 1 )
        sequence[c] = new BigInteger( Integer.toString( c ) );
      else
      {
        sequence[c] = sequence[c - 1].add( sequence[c - 2] );
        sequence[c - 2] = null;
        if ( c %( n / 100 ) == 0 )
          System.out.printf( "\r%d%%", c / ( n / 100 ) );
      }
    }
    System.out.println();
    return sequence[n];
  }
  
  public static void main( String args[] )
  {
    Scanner input = new Scanner( System.in );
    int choice = 0;
    boolean read = false;
    System.out.print( "Insira o número da sequencia de fibonacci desejado: " );
    
    do
    {
      try
      {
        choice = input.nextInt();
        read = true;
      }
      catch( InputMismatchException e )
      {
        System.out.printf( "Error reading the number..." );
      }
      catch( NoSuchElementException e )
      {
        System.out.printf( "Error reading the number..." );
      }
    }while ( read == false );
    try
    {
      System.out.print( fibonacci( choice ) );
    }
    catch( OutOfMemoryError e )
    {
      System.out.printf( "Not enought Memory available... Program will finish." );
      System.exit( 1 );
    }
  }
}

Eu gostaria de ver se alguem pode me ajudar com algumas duvidas:

Uma variavel ocupa espaço? Ou é so o valor delas? Um bigInteger null vai ocupar alguma memoria?
Eu testar todos os valores para saber se tem resto 0 ( Para imprimir na tela a porcentagem concluida ) ocupa algum processamento significativo?
++a é mais rapido que um a++ em um cabeçalho de for?
Exista algo que eu possa fazer para aumentar o desempenho e a velocidade do processamento desse programa?

Obrigado a todos

Infelizmente, conforme você pode comprovar, o Java não é adequado para métodos com alto grau de recursividade, porque ele guarda as variáveis locais na pilha (stack) e a pilha é, por default, muito pequena (128 K no Windows). Você pode tentar usar a opção -Xss para aumentar a pilha das threads que não são a thread principal, mas mesmo assim você acabará chegando a um teto relativamente baixo.

O Java poderia usar uma otimização que se chama “tail call” para não consumir espaço no stack, mas infelizmente ele não faz isso ainda.

Tente ver se você pode reescrever seu programa em Scala, de modo que ele use essa otimização de tail calls, para obter graus de recursividade maiores.


Uma variável local ocupa usualmente 8 bytes no stack, porque essa é a mínima granularidade (em um processador x86 ou Sparc ou MIPS) para referenciar uma variável no stack; mesmo sendo uma variável de referência. Obviamente, se a variável tiver um tipo objeto (por exemplo, um java.math.BigInteger) fora o espaço ocupado no stack, o BigInteger correspondente ocupará espaço no heap.

Só a sua referência “null” no stack.

Hoje em dia isso só é significativo em processadores de pocket pcs/palms, não em PCs ou notebooks.

Não, porque gera exatamente os mesmos bytecodes.

Você pode usar “memoization” conforme você mesmo deve já ter percebido.

http://www.guj.com.br/posts/list/90054.java

Você só precisa usar BigInteger no cálculo do número de Fibonacci se for calcular para n > 93.

Não acredito que fiz isso asuhaushauhs… Vlw pelas dicas

De qualquer maneira, pode-se usar a fórmula “fechada” para obter um termo da sequência de Fibonacci:

(veja em http://en.wikipedia.org/wiki/Fibonacci_number )

Ou seja, digamos que você queira achar F (1000000). Você sabe, por essa fórmula, que F (1000000) deve ser aproximadamente igual a:

5,6972870192248182216556367683049 x 10 elevado a 338148

ou seja, o número tem 338149 dígitos.

Você pode usar esta fórmula:

e na verdade seu problema é achar uma forma de calcular
com 338160 dígitos, elevar esse valor a 1000000 (que é relativamente rápido; não exige 1000000 multiplicações, mas bem menos - na verdade, apenas 26 multiplicações), e então dividir o valor por raiz de 5 com 338160 dígitos.

Você pode usar uma fórmula de raiz quadrada (não existe pronto no BigDecimal) para calcular a raiz de 5, que você irá precisar de qualquer maneira para calcular phi com 338160 casas.

Usando o método de potências da matriz [(1,1),(1,0)] não é mais eficiente(ou pelo menos mais simples pois não será necessário recorrer a radiciação)?

Até!

Dijsktra (sempre ele!) achou um método de calcular rapidamente um número de Fibonacci, com uma quantidade limitada de operações.

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html#exact

Por exemplo, nosso número F(1000000) iria requerer calcular os seguintes números de Fibonacci:

F(1000000) requer saber F(500000) e F(499999)
F(500000) e F(499999) requer saber F(250000) e F(249999)
F(250000) e F(249999) requer saber F(125000)…
F(125000) … requer saber F(6250)…
F(6250) … F(3125)
F(3125) … F(1562)
e assim por diante, até sabermos F(1) e F(1).

[quote=Polimorphism]Olá, estou desenvolvendo um programa de fibonacci, para aprender na pratica um pouco sobre desempenho, e estou tentando desenvolver um que alcançe numeros cada vez maiores. Primeiro usei um metodo recursivo, que achei no java como programar, so que so depois de 50 começava a dar erro de StackOverFlow.
Então resolvi quardar os resultados em um array, dai consegui chegar ate 1000.
Depois resolvi fazer o programa calcular todos, do 0 até o numero escolhido, para acabar com o StackOverFlow. O Programa chegou ate 10.000.
Depois disso ví que o problema não era processamento, e sim muita coisa na memoria. Resolvi que a cada vez que o fibonacci achava mais um numero, deveria apagar o bigInteger que ficava dois atrás, que não seria mais util.

Apos saber fibonacci 5, pode se apagar fiboancci 3, já que o 6, so vai ter que saber quanto é o 4 + o 5. Isso ajudou e agora o programa pode calcular qualquer resultado, o que as vezes pode demorar. Vou postar o codigo

public class FibonacciSequence
{
  public static BigInteger fibonacci( int n )
  {
...
  }
  
  public static void main( String args[] )
  {
...
  }
}

Eu gostaria de ver se alguem pode me ajudar com algumas duvidas:

Uma variavel ocupa espaço? Ou é so o valor delas? Um bigInteger null vai ocupar alguma memoria?
Eu testar todos os valores para saber se tem resto 0 ( Para imprimir na tela a porcentagem concluida ) ocupa algum processamento significativo?
++a é mais rapido que um a++ em um cabeçalho de for?
Exista algo que eu possa fazer para aumentar o desempenho e a velocidade do processamento desse programa?

Obrigado a todos[/quote]
Tentei um valor baixo (5) e deu erro de divisão por zeros hehehehe…

if ( c %( n / 100 ) == 0 )

Pode haver tbm um problema no método add de BigInteger que pode determinar tbm a perda de performance.
Vc pode utilizar alguns logs para verificar qual o ponto de perda de performance.

Qto ao problema de pilha, existem varias formas de tunning da memória por parâmetros, inclusive do GC.

Fiz uma pequena alteração no código:

    ArrayList<BigInteger> intSequence = new ArrayList<BigInteger>(4);
    
    intSequence.add(new BigInteger( Integer.toString( 0 )));
    intSequence.add(new BigInteger( Integer.toString( 1 )));
    for(int i = 2; i < n+1 ; ++i){
		intSequence.add(intSequence.get(0).add(intSequence.get(1)));
		intSequence.remove(0);
//		if ( n > 100 && i %( n / 100 ) == 0 ){   // coloquei uma conscistência pois quando n menor que zero, n/100 = 0
//			System.out.printf( "\r%d%%", i / ( n / 100 ) );
//		}
    }
//    System.out.println();
    return intSequence.get(intSequence.size()-1);

A partir de números maiores houve um ganho mínimo no tempo e, aparentemente há uma perda sensível no add do BigInteger.
Sugestão: Criar uma classe que substitua o BigInteger onde o add possa ser otimizado.