Блог пользователя Limie

Автор Limie, история, 3 месяца назад, По-английски

How to quickly find the value of each item in the following sequence.

$$$a_n=\lfloor (1+\sqrt{3})^n \rfloor$$$

Calculated in the sense of taking a mode.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Limie (previous revision, new revision, compare).

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Do you want to calculate all the values from 1 to n? or just for specific large n values?
It looks like you got this from the formula a_n = 2*(a_(n-1)+a_(n-2)).
If you want all values from 1 to n that'l take at least O(n) anyway so then use the recurrence

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I only want to calculate one values.

    • »
      »
      »
      3 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      then given the fact we know its equal to this recurence, we can use matrix exponentiation to calculate values in O(logn)
      here's a post that explains about this a bit more.

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

But it's fast enough, since it's exponiental, it will only be calculted in log(n). Or is the problem of float relative error, if yes can you provide the equation that have this number as solution?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Limie (previous revision, new revision, compare).