Fibonacci数の高速計算法
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, Fibonacci数を高速に計算する方法について述べる.Fibonacci数F_nを計算するに葉, Lucas数の積に基づくアルゴリズムが, 最もビット演算量が少ないことが知られている.このアルゴリズムにおいて, 多倍長数の乗算を多倍長数の自乗計算に置き換えることで, さらに演算量を減らすことができることを示す.
- 2000-06-15
著者
関連論文
- HMCS-G : グリッド環境における計算宇宙物理のためのハイブリッド計算システム(グリッド応用)
- 演算加速機構を持つオンチップメモリプロセッサの電力性能評価(ARC-3 : 性能評価およびモデリング,2007年並列/分散/協調処理に関する『旭川』サマー・ワークショップ(SWoPP旭川2007))
- T2K筑波システムにおけるLinpack性能評価(HPC-4:性能評価,2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ(SWoPP佐賀2008))
- Short Vector SIMD命令を用いた並列FFTの実現と評価(性能最適化)
- 大規模固有値問題のmaster-worker型並列解法(数値計算)
- OmniRPCによるグリッド環境での大規模固有値問題の並列解法(数値アルゴリズム)
- "FIRST"-第一世代天体の起源解明のための専用・汎用計算機融合型クラスタ(HPC-8: 高性能クラスタ)
- EthernetマルチリンクによるPCクラスタ向け高バンド幅・耐故障ネットワークRI2N/UDP(ネットワーク)
- tagged-VLANとマルチリンクに基づくPCクラスタ向け高性能・耐故障ネットワークの実装と評価(Session 3:Cluster/Grid)
- VFREC-Net : ドライバ制御によるtagged-VLANを用いたPCクラスタ向けマルチパスネットワーク(ネットワーク)
- EthernetマルチリンクによるPCクラスタ向け耐故障ネットワークRI2N/UDP(ネットワーク,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2006))
- EthernetマルチリンクによるPCクラスタ向け耐故障ネットワークRI2N/UDP(ネットワーク, 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2006))
- tagged-VLANに基づくPCクラスタ向け高バンド幅ツリーネットワークの開発(HPCシステム)
- Etheretによるクラスタ上での分散共有メモリOpenMP Omni/SCASHの性能評価
- オンチップメモリプロセッサでの演算加速機構の検討(プロセッサ・アーキテクチャ(2),「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- PCクラスタにおける電力実行プロファイル情報を用いたDVS制御による電力性能の最適化(クラスタシステム)
- PCクラスタにおける電力実行プロファイル情報を用いたDVS制御による電力性能の最適化(省電力,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2006))
- PCクラスタにおける電力実行プロファイル情報を用いたDVS制御による電力性能の最適化(省電力, 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2006))
- 高性能計算のための低電力・高密度クラスタMegaProto(HPCハードウェア)
- PCクラスタにおけるDVS制御による電力性能の最適化(ARC-3: 低電力アーキテクチャ1, 2005年並列/分散/協調処理に関する『武雄』サマー・ワークショップ(SWoPP武雄2005)-研究会・連続同時開催-)
- 高性能計算のための低電力・高密度クラスタMegaProto(クラスタと通信, 分散処理, 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- オンチップメモリプロセッサでの演算加速機構の検討(プロセッサ・アーキテクチャ(2),「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- 積和演算命令に向いた8基底FFTカーネルの提案
- 級数に基づく多数桁計算の演算量削減を実現する分割有理数化法
- 積和演算に向いた8基底FFT Kernelの提案
- 無限級数に基づく多数桁計算の演算量削減を実現する分割有理数化法 (数値計算における前処理の研究)
- 分散メモリ型並列計算機による円周率の515億桁計算
- 分散メモリ型並列計算機による2, 3, 5基底一次元FFTの実現と評価
- 多数桁の円周率を計算するための公式の改良 : ガウスールジャンドルの公式とボールウェインの4次の収束の公式
- 分散メモリ型並列計算機による円周率の高精度計算
- 並列計算機における二次記憶を用いた一次元FFTの実現と評価
- 分散メモリ型並列計算機による多倍長平方根の高速計算法
- 分散メモリ型並列計算機による2, 3, 5基底のFFTの実現と評価
- 分散メモリ型並列計算機による高速多倍長計算
- 多倍長平方根の高速計算法
- 行列積を用いた古典Gram-Schmidt直交化法の並列化
- PACS-CSにおける隣接通信性能の高速化(HPC-13 : 通信II)
- PACS-CSのための高性能通信ライブラリインターフェイスの設計(HPC-12 : 大規模運用システム(2))
- 行列積を用いた古典Gram-Schmidt直交化の並列化手法の検討(数値計算2)
- 演算加速機構を持つオンチップメモリプロセッサの検討と電力性能評価
- DVFS制御を目的としたプログラムの領域分割(Session 6:低消費電力)
- MegaProto/Eにおける電力性能評価および電力性能最適化の検討(Session 6:低消費電力)
- DVS制御による負荷不均衡のある並列プログラムの電力量削減手法(クラスタシステム)
- PCクラスタにおける全体電力プロファイルを用いた電力性能最適化(ARC-1:低電力アーキテクチャ,2006年並列/分散/強調処理に関する『高知』サマー・ワークショップ(SWoPP 高知2006))
- DVS制御による負荷不均衡のある並列プログラムの電力量削減手法(省電力,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2006))
- DVS制御による負荷不均衡のある並列プログラムの電力量削減手法(省電力, 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2006))
- 科学技術計算用超並列クラスタPACS-CSの実装と基本性能評価(HPC-12 : 大規模運用システム(2))
- 超並列クラスタにおける3D-RISMへのVolumetric並列三次元FFTの適用と性能評価
- オンチップメモリプロセッサでの演算加速機構の検討 (計算機アーキテクチャ・ハイパフォーマンスコンピューティング 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2007))
- 複数グリッドジョブ実行システムの計算資源を統合・利用するGrid RPCシステムの設計と実装(グリッドシステム)
- グリッドRPCシステムOmniRPCにおける初期データの分散管理による効率化(グリッドRPC)
- オンチップRAM利用による電力性能の最適化と評価(ARC-3: 低電力アーキテクチャ1, 2005年並列/分散/協調処理に関する『武雄』サマー・ワークショップ(SWoPP武雄2005)-研究会・連続同時開催-)
- プロセッサの消費電力測定と低消費電力プロセッサによるクラスタの検討(省電力)
- 低消費電力プロセッサによるクラスタの検討(ARC-6:低消費電力化)(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- HPC向けオンチップメモリプロセッサアーキテクチャSCIMAのSMP化の検討と性能評価
- HPC向けオンチップメモリプロセッサアーキテクチャSCIMAのSMP化の検討と性能評価
- 複数グリッドミドルウエア上で動作するGrid RPCシステムOmniRPCの設計と実装(HPC-4: グリッド)
- P2P分散システムXtremWeb上でのGrid RPCシステムOmniRPCの設計(HPC-7 : グリッド(2))(2004年並列/分散/協調処理に関する『青森』サマー・ワークショップ(SWoPP青森2004) : 研究会・連続同時開催)
- CONFLEX-G : OmniRPCによるグリッド環境上での分子立体配座探索プログラムの実装と性能評価(グリッド応用)
- OmniRPCによる広域ネットワーク環境でのグリッドアプリケーションの性能評価(HPC-5 : グリット(1))(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- OmniRPCによるグリッド環境での大規模固有値問題の並列解法 (数値解析と新しい情報技術)
- 重力計算専用計算機GRAPE-6のリモートアクセス環境(HPC環境とその応用)
- 演算加速装置に基づく超並列クラスタHA-PACSによる大規模計算科学
- MPIを通信レイヤに用いるソフトウェア分散共有メモリシステム(ソフトウエアDSM)
- ヘテロなクラスタ環境におけるStrassenの行列積アルゴリズムの並列化(数値計算)
- MPI上のソフトウェア分散共有メモリシステム(並列処理のためのシステム)
- OmniRPC : グリッド環境での並列プログラミングのためのGrid RPCシステム(グリッド基盤ソフト)
- Omni/SCASHおけるFirst Touch page allocation の実装(ARC-9:ハイパフォーマンスコンピューティング)(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- 高バンド幅/耐故障性を持つクラスタ向けネットワークRI2Nの性能評価(HPC-4 : ネットワーク)(2003年並列/分散/協調処理に関する『松江』サマー・ワークショップ(SWoPP松江2003))
- ユーザレベルでのマルチリンク利用による高バンド幅/耐故障性を持つクラスタ向け結合ネットワークRI2N
- ヘテロなクラスタ環境におけるStrassenの行列積アルゴリズムの並列化
- OmniRPC : グリッド環境での並列プログラミングのためのGrid RPCシステム(高性能計算及び一般)
- ItaniumプロセッサによるSCoreクラスタ構築に関する検討(高性能計算及び一般)
- SMP-PCクラスタにおけるSPAM粒子シミュレーションのハイブリッド並列化
- PCクラスタにおける並列一次元FFTのブロックアルゴリズム
- 共有メモリ型並列計算機における並列FFTのブロックアルゴリズム(並列処理)
- SR8000におけるOpenMPベンチマーク
- SR8000におけるOpenMPベンチマーク
- SMPクラスタにおける並列FFTのブロックアルゴリズム
- 拡張split-radix FFT アルゴリズム
- Fibonacci数の高速計算法
- 並列言語XcalableMPのアクセラレータ向け言語拡張のOpenCL実装
- 大規模GPUクラスタにおけるN体計算コードの演算性能とスケーラビリティの評価