問題タブ [logarithm]

ウィキペディアのウェーブレットの記事には、次のテキストが含まれています。

離散ウェーブレット変換も計算が複雑ではなく、高速フーリエ変換のO（N log N）と比較してO（N）時間がかかります。この計算上の利点は、変換に固有のものではありませんが、FFTの等間隔の周波数除算とは対照的に、周波数の対数除算の選択を反映しています。

これは、線形ではなく周波数の対数除算を使用するFFTのようなアルゴリズムもあることを意味しますか？O（N）でもありますか？これは、多くのアプリケーションにとって明らかに望ましいことです。

yの対数目盛を使用してRでヒストグラムを生成しようとしています。現在私はします：

これによりヒストグラムが得られますが、0から1までの密度は非常に大きいため（約100万の値の差）、他のバーをほとんど理解できません。

それから私はやってみました：

必要なものが表示されますが、下部には0、1、2、3、4、5、25ではなく1〜6の値が表示されます。また、データはバーではなくポイントとして表示されます。barplot動作しますが、下軸が表示されません。

今日、私はかなり奇妙な問題に遭遇しました。数値の文字列の長さを計算する必要があったので、この解決策を思いつきました

これは数式に基づいています

log₁₀ x = log_n x/log_n10 (ここで説明)

しかし、Cでは、

等しくない_

しかし、そうあるべきです。

このコードを使用してJavaで同じことを試しました

しかし、それは同じ間違った方法で動作します。

話は続きます。このコードを実行した後

私は得る

したがって、バグは 1000 の倍数ごとに発生するようです。

これをCの先生に見せたら、対数除算時の型変換ミスが原因かもしれないと言われましたが、原因がわかりませんでした。

だから私の質問は

• 数学によると、そうあるべきなのに、なぜ は(int) (Math.log(1000) / Math.log(10)) + 1と等しくないのですか。(int) Math.log10(1000) + 1
• 1000の倍数だけ間違っているのはなぜですか?

編集：丸め誤差ではありません。

同じ間違った出力を生成する

edit2:桁数を知りたいので切り捨てます。

丸めただけでも同じ結果 (4) が得られますが、999 は 3 桁なので間違っています。

次の方法で任意の数値をパーセンテージに変換する方法を探しています。

1. 1.00 は 50%

2. 1.00 未満の数値は対数的に 0% に近づきます

3. 1.00 を超える数値は、対数的に 100% に近づきます。

   x > 0. x が正の側で無限に小さくなるので、y は 0 に近づく必要があります。

これは簡単にできると思いますが、その方法を思い出せません。

2 の累乗であることがわかっている数値の 2 を底とする対数を取得するための最適なソリューションは何ですか ( 2^k)。(もちろん、私はそれ自体では2^kなく値だけを知っていkます。)

私が考えた 1 つの方法は、1 を減算してからビットカウントを行うことです。

しかし、（キャッシュなしで）それを行うより速い方法はありますか？また、ビットカウントがそれほど速くないことを知っておくといいですか?

これは次のアプリケーションの 1 つです。

キャッシュなしでbitcountよりも高速であるためO(lg(k))にkは、ストレージ ビットのカウントよりも高速である必要があります。

Ada の使用 (GNAT): 特定の値の 10 のべき乗を決定する必要があります。最も明白なアプローチは、対数を使用することです。しかし、それはコンパイルに失敗します。

エラー：

• utility.adb:495:26: 「ログ」が表示されない
  • utility.adb:495:26: a-ngelfu.ads:24 の非表示宣言、482 行のインスタンス
  • utility.adb:495:26: a-ngelfu.ads:23 の非表示宣言、482 行目のインスタンス

そのため、パッケージを参照しようとしましたが、それも失敗しました:

エラー：

• utility.adb:495:41: 候補の解釈が実際のものと一致しません:
• utility.adb:495:41: "Log" の呼び出しで引数が多すぎます
• utility.adb:495:53: 期待される型 "Standard.Float"
• utility.adb:495:53: a-ngelfu.ads:24 の「Log」の呼び出しで型の汎用整数 ==> が見つかりました、482 行目のインスタンス

ビット演算のみを使用して2の累乗から指数を抽出する簡単な方法はありますか？

編集：質問はもともとビット演算に関するものでしたが、 「 PythonでY = 2 Xの場合にXを見つける最も速い方法は何ですか？」**

私は現在、フォームの偶数Nを減らすルーチン（ Rabin-Miller素数性テスト）を最適化しようとしています。私は次の方法で部品を入手できます：2**s * d2**s

しかし、ビット演算で「 s 」だけを抽出する方法が見つかりません。私が現在あまり満足せずにテストしている回避策（それらはすべてかなり遅いです）は次のとおりです。

• 対数関数を使用する
• 2 **のバイナリ表現を操作する（つまり、末尾のゼロを数える）
• 結果が1になるまで2で除算をループします

私はPythonを使用していますが、この質問に対する答えは言語に依存しないはずです。

分数のリストが 2 つあります。

いうA = [ 1/212, 5/212, 3/212, ... ]

とB = [ 4/143, 7/143, 2/143, ... ]。

と定義するA' = a[0] * a[1] * a[2] * ...とB' = b[0] * b[1] * b[2] * ...

の値を計算したいのですがA' / B'、

私の問題は、A と B の両方が非常に長く、各値が小さいため、積を計算すると数値のアンダーフローが非常に速く発生することです...

積を対数で和にすると、A' と B' のどちらが大きいかを判断するのに役立つことを理解しています

すなわちmax( log(a[0])+log(a[1])+..., log(b[0])+log(b[1])+... )

しかし、私は実際の比率が必要です....

これまでの私の最善の策は、数値表現を分数として保持することです。つまりA = [ [1,212], [5,212], [3,212], ... ]、独自の算術演算を実装しますが、不器用になり、欠けている対数の（単純な）方法があると感じています....

A と B の分子は数列に由来しません。この質問の目的のために、それらはランダムである可能性もあります。B のすべての分母と同様に、A のすべての値の分母が同じになるのに役立つ場合。

どんなアイデアでも大歓迎です！

マット

分数のリストが 2 つあります。

いうA = [ 1/212, 5/212, 3/212, ... ]

とB = [ 4/143, 7/143, 2/143, ... ]。

と定義するA' = a[0] * a[1] * a[2] * ...とB' = b[0] * b[1] * b[2] * ...

A' と B' の正規化された値を計算したい

つまり、具体的にはA' / (A'+B')と の値B' / (A'+B')

私の問題は、A と B の両方が非常に長く、各値が小さいため、積を計算すると数値のアンダーフローが非常に速く発生することです...

積を対数で和にすると、A' と B' のどちらが大きいかを判断するのに役立つことを理解しています

すなわちmax( log(a[0])+log(a[1])+..., log(b[0])+log(b[1])+... )

ログを使用して値を計算できますがA' / B'、どうすればよいですかA' / A'+B'

これまでの私の最善の策は、数値表現を分数として保持することです。つまりA = [ [1,212], [5,212], [3,212], ... ]、独自の算術演算を実装しますが、不器用になり、欠けている対数の（単純な）方法があると感じています....

A と B の分子は数列に由来しません。この質問の目的のために、それらはランダムである可能性もあります。B のすべての分母と同様に、A のすべての値の分母が同じになるのに役立つ場合。

どんなアイデアでも大歓迎です！

( ps. 24 時間前に比率に関して同様の質問A'/B'をしましたが、実際には間違った質問でした。実際には の後A'/(A'+B')です。申し訳ありませんが、私の間違いです。)