Рекурсивная Фибоначчи в тексте WebAssembly - PullRequest
Новая
       15

Рекурсивная Фибоначчи в тексте WebAssembly

0 голосов
/ 21 ноября 2018

Я играл с текстом WebAssembly и хотел написать рекурсивный калькулятор чисел Фибоначчи.

Я получил версию, которая работает, но она использует одну ветвь оператора if для проверки базового случая: 

(module
 (export "fib" (func $fib))
  (func $fib (param $0 i32) (result i32)
  (if
   (i32.lt_s
    (get_local $0)
    (i32.const 2)
   )
   (return
    (i32.const 1)
   )
  )
  (return
   (i32.add
    (call $fib
    (i32.sub
      (get_local $0)
      (i32.const 2)
    )
   )
    (call $fib
      (i32.sub
       (get_local $0)
       (i32.const 1)
     )
    )
   )
  )
 )
)

Я проверил это в wabt здесь: https://webassembly.github.io/wabt/demo/wat2wasm/

Я попытался переписать это, используя условное выражение: 

(module
       (export "fib" (func $fib))
     (func $fib (param $0 i32) (result i32)
            (select
                   (return
                    (i32.const 1)
                    )
                  (return
                   (i32.add
                    (call $fib
                          (i32.sub
                           (get_local $0)
                           (i32.const 2)
                           )
                          )
                    (call $fib
                          (i32.sub
                           (get_local $0)
                           (i32.const 1)
                           )
                          )
                    )
                   )
                (i32.lt_s
                 (get_local $0)
                 (i32.const 2))))
     )

Это компилируется в .wasm, но этоне работает, как ожидалось, просто возвращает базовый вариант.Я пробовал похожие версии с if-then-else, но безрезультатно.Почему результат одного ветвления будет отличаться от условного с двумя ветвями?

1 Ответ

0 голосов
/ 21 ноября 2018

Вы только что дали мне причину учить вас.Я пока не могу ответить на ваш вопрос об одной ветви if, но я могу показать вам работающую fib функцию. 

(module
  (func $fib2 (param $n i32) (param $a i32) (param $b i32) (result i32)
    (if (result i32)
        (i32.eqz (get_local $n))
        (then (get_local $a))
        (else (call $fib2 (i32.sub (get_local $n)
                                   (i32.const 1))
                          (get_local $b)
                          (i32.add (get_local $a)
                                   (get_local $b))))))

  (func $fib (param i32) (result i32)
    (call $fib2 (get_local 0)
                (i32.const 0)   ;; seed value $a
                (i32.const 1))) ;; seed value $b

  (export "fib" (func $fib)))

Копировать / вставить, чтобы продемонстрировать ее здесь 

const wasmInstance =
  new WebAssembly.Instance (wasmModule, {})

const { fib } =
  wasmInstance.exports

for (let x = 0; x < 10; x = x + 1)
  console.log (fib (x))

Вывод 

0
1
1
2
3
5
8
13
21
34

Реализация здесь совершенно иная, чем у вас.Ваша программа требует экспоненциального вычислительного времени и пространства, тогда как требования вышеупомянутой программы линейны.

Это видно из изучения использования (call $fib ...).В вашей программе один вызов на $fib имеет возможность порождать два дополнительных вызова на $fib, каждый из которых имеет возможность порождать два дополнительных вызовов на $fib, и так далее.Выше $fib2 имеет потенциал только для вызова один раз , самое большее.

Хотя он имеет меньшую производительность, конечно, он все еще возможен дляреализовать экспоненциальный процесс 

(module
  (func $fib (param $n i32) (result i32)
    (if (result i32)
        (i32.lt_s (get_local $n)
                  (i32.const 2))
        (then (get_local $n))
        ;; recursive branch spawns _two_ calls to $fib; not ideal
        (else (i32.add (call $fib (i32.sub (get_local $n)
                                           (i32.const 1)))
                       (call $fib (i32.sub (get_local $n)
                                           (i32.const 2)))))))

  (export "fib" (func $fib)))
...