Skip to content
TheChatArchiveThe Chat Archive
Geminigemini-pro-dev-api· GoogleHugging Face Arena Human Preference 55K

Code for computing fib numbers in log time

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with gpt-4-0613’s answer.
  1. User

    Code for computing fib numbers in log time

  2. Gemini Assistant
    def fib_log_time(n):
      """Computes the nth Fibonacci number in log time.
    
      Args:
        n: The index of the Fibonacci number to compute.
    
      Returns:
        The nth Fibonacci number.
      """
    
      # Base cases
      if n == 0:
        return 0
      if n == 1:
        return 1
    
      # Compute the Fibonacci numbers of the two halves of n.
      k = n // 2
      f_k = fib_log_time(k)
      f_k_plus_1 = fib_log_time(k + 1)
    
      # Compute the nth Fibonacci number using the matrix multiplication formula.
      return f_k * f_k_plus_1 + f_k_plus_1 * f_k_plus_1
    
    
    # Example usage
    n = 10
    result = fib_log_time(n)
    print(f"The {n}th Fibonacci number is {result}")
    

    The time complexity of this algorithm is O(log n), which is significantly faster than the naive recursive algorithm, which has a time complexity of O(2^n). This is because the recursive calls are made on the two halves of n, rather than the entire number. As a result, the number of recursive calls is reduced by a factor of 2 at each level of the recursion, leading to a logarithmic time complexity.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.