C言語なら俺に聞け 153

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん (ﾜｯﾁｮｲ 5fba-LL4R)
垢版 |
2019/08/17(土) 23:02:42.00ID:tN5mSQYg0
C言語の話題のみ取り扱います C++の話題はC++スレへ
質問には最低限の情報(ソース/コンパイラ/OS)を付ける
数行で収まらないソースは以下を適当に使ってURLを晒す
https://paiza.io/
https://ideone.com/
http://codepad.org/

C11
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf

C99
http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf
http://kikakurui.com/x3/X3010-2003-01.html

C FAQ 日本語訳
http://www.kouno.jp/home/c_faq/

JPCERT C コーディングスタンダード
https://www.jpcert.or.jp/sc-rules/
-
VIPQ2_EXTDAT: checked:vvvvv:1000:512:----: EXT was configured
※前スレ
C言語なら俺に聞け 152
https://mevius.5ch.net/test/read.cgi/tech/1560763630/
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
2019/12/02(月) 14:34:46.17ID:1jC9vBnEx
フーリエは本来可逆だ。
2019/12/02(月) 14:52:09.59ID:xJykAg3Zd
圧縮が目的でフーリエ変換するのに
何も情報を減らさずにそのまま戻してどうする？
2019/12/02(月) 14:53:09.69ID:xJykAg3Zd
>>441
心配しなくても
ナイキスト周波数を越える成分はフーリエ変換の結果には含まれない
445デフォルトの名無しさん (ﾜｲｰﾜ2 FF1a-YC6P)
垢版 |
2019/12/02(月) 14:56:19.28ID:9YVAThVAF
>>423
>>426
離散コサイン変換じゃいかんのか
446デフォルトの名無しさん (ﾜｲｰﾜ2 FF1a-YC6P)
垢版 |
2019/12/02(月) 14:59:03.83ID:9YVAThVAF
>>432
どうせ課題なんだしそこまで求めてないというか
もしすごいのが出来たら教授が自分の成果にして発表するんやろ
447デフォルトの名無しさん (ｴﾑｿﾞﾈ FFb2-YC6P)
垢版 |
2019/12/02(月) 15:03:30.60ID:HSnksJTzF
>>442
ほんそれ

ただし無限な
2019/12/02(月) 15:04:01.88ID:ImcNE8i40
スゴイの出来たら、先に特許申請だな
2019/12/02(月) 15:06:19.88ID:R6hiSLip0
講義での学習課題としては非圧縮でないと判定が面倒だな
単にデータを間引いただけなのか演算を間違っているのか確認に手間が掛かる
むしろ完全可逆で実装した方が採点する側としては分かりやすいだろう
出題者の意図はどこにあるか質問者は理解しているのだろうか？
2019/12/02(月) 15:16:11.81ID:az4xQt0G0
なんで理解しなきゃいけねーの
そういう旨なら文章にハッキリ書いてくれねーと困るワケ
お気持ちを察せよ　なんてのが罷り通る案件なの？
2019/12/02(月) 15:18:11.07ID:az4xQt0G0
「オメーの気持ちなんてしったこっちゃねー
　オレに分かるように話せ」
が今の潮流

分からないように反為さないヤツは無視していいし排除していい
なんつったってオレが理解出来ないヤツは何言ってるか分からないコミュニケーション不可能な敵に近いからな
気持ち悪いから排除してもいいし、何よりオレに理解されようと思ってない
だから排除していいでしょ

……という思考で動くのが現代の日本社会
2019/12/02(月) 15:21:55.25ID:R6hiSLip0
いやクライアントの意向を無視して好き勝手やっていたら仕事干されるだろ
2019/12/02(月) 16:43:27.43ID:cSs5r0tn0
保存とは書かれているが圧縮とはどこにも書かれてない件
2019/12/02(月) 16:47:13.54ID:wj2s3ic80
てか皆さん「フーリエ変換くらい当然知ってる」って雰囲気なのが凄いわ。
2019/12/02(月) 17:56:06.03ID:kmSxls5X0
>>453
>>425,426
2019/12/02(月) 18:01:01.74ID:kmSxls5X0
圧縮しないなら
保存でフーリエ変換使う意味がわからんがな
2019/12/02(月) 18:04:51.11ID:R6hiSLip0
フーリエ変換そのものは理系の大学卒であれば誰でも知ってる
具体的な数値計算のアルゴリズムを知っているかはその人の専門分野による
2019/12/02(月) 18:35:35.76ID:PAbfC2b00
理系でも生物系なら触りもせん
2019/12/02(月) 18:53:16.42ID:R6hiSLip0
専門課程ではなくても一般教養の数学系の講義で学んでると思うけど
2019/12/02(月) 19:00:10.22ID:PAbfC2b00
微積と線形代数ぐらいで触らんかったぞ
大学なんか講師次第だからなあ
2019/12/02(月) 19:09:01.78ID:ImcNE8i40
文系だと無いと思うな
統計学や代数幾何、微積分
この辺まで
2019/12/02(月) 19:11:47.56ID:CL9/qeyha
はるか前なので忘れたが、大学ではフーリエ級数って名前だった希ガス
2019/12/02(月) 19:12:24.77ID:kmSxls5X0
理系の大学卒だが
フーリエ変換を大学で習った記憶はないなあ
覚えてないだけかな？
2019/12/02(月) 19:40:44.78ID:R6hiSLip0
フーリエ変換はフーリエ級数展開の一般化
フーリエ級数展開の基本周期を無限大まで拡大すると周波数成分は離散から連続となる
要するに周波数成分を連続スペクトルとして扱うのがフーリエ変換
2019/12/03(火) 19:46:15.44ID:90Sp73uqM
画像のフーリエ変換なんてどうやってやるんだ？って思ってググったら結構面白いな
ちょっと実装してみよう
https://algorithm.joho.info/image-processing/fourier-transform/
2019/12/03(火) 22:43:48.90ID:nrVtlETj0
数学科院卒だがフーリエ変換には掠りもしてない
工学部の一部しか触ってないだろう
2019/12/04(水) 02:04:25.88ID:k3euaH00M
数学的には解析学の領域
どちらかといえば数学と物理の境界
電気工学や情報工学では必須
https://ja.wikipedia.org/wiki/%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B
2019/12/04(水) 02:24:25.40ID:k3euaH00M
工学部では厳密な理論よりも応用が重要なので表面的な触りだけで深入りはしない
厳密な議論はやはり数学者の分野だと思う
2019/12/04(水) 09:27:46.76ID:bVbh++oq0
画像処理はOpenCVとかで済ましちゃうから細かい数式は気にしない
2019/12/04(水) 09:38:25.43ID:ayTFyO7RM
それには同意
フーリエ変換の利用にはFFTの概要だけ理解していれば十分
ただ数学の専門家が掠りもしてないというのは如何なものかとは思う
2019/12/04(水) 10:58:24.04ID:9VaeVeX00
Wikipedia繋がりでFFTのリンク開いてみるとVisualBasicでの実装例が掲載されてるね
https://ja.wikipedia.org/wiki/%E9%AB%98%E9%80%9F%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B
2019/12/04(水) 13:12:26.50ID:6uL3pMIBd
>>468
数学的にはとっくの昔に解決してるから
あとは工学系の仕事
2019/12/04(水) 13:15:06.38ID:6uL3pMIBd
>>470
応用数学とかそういう分野ならまだしも
純粋な数学者はそんなことには興味がない
2019/12/04(水) 13:17:30.35ID:6uL3pMIBd
FFTはアルゴリズムの名前
2019/12/04(水) 13:33:37.43ID:ayTFyO7RM
ラプラス変換やz変換あたりだと完全に工学分野だけどフーリエ変換くらい汎用なものは数学分野でも活用されてると思うけどね
フーリエ級数はローラン級数などと同じ複素解析の基本的な考え方でしょ
べきに展開するか指数に展開するかの違いくらいのもの
2019/12/04(水) 13:59:41.66ID:6uL3pMIBd
>>475
>>472
2019/12/04(水) 14:02:42.65ID:kZk+LcEC0
無理を言ってはいけない
数学者には楽器は作れても名曲を作る事はできない
2019/12/04(水) 15:03:29.21ID:49y1id9ud
名曲を作るのは数学者でも物理学者でも工学博士でもない
発明家や企業だ
479デフォルトの名無しさん (ｱｳｱｳｳｰ Sacd-8Irb)
垢版 |
2019/12/04(水) 21:02:14.66ID:wHBVaWfta
沖縄音階は適当にランダムに音出しても曲に聞こえちゃうけどな
2019/12/04(水) 22:00:13.57ID:Ibv81ciOa
>>479
それは沖縄音階に馴染みがないから、沖縄音階が使われているだけで沖縄っぽいと感じてるだけなんじゃないかな？
沖縄の人からしたら、そんなデタラメでは曲として成り立ってないと思わないのかな。
2019/12/05(木) 00:53:08.83ID:MEu1VAiTM
そういった抽象的な感覚を数値化して扱うための手段がフーリエ解析やスペクトル解析と呼ばれる分野
音楽の音階(周波数)やリズム(時系列)を分解して客観的に評価するのが科学的なアプローチ
2019/12/05(木) 03:51:45.82ID:6S4oFaeF0
>>481
どちらかといえばウェーブレット解析の方が適しているような気がする
フーリエ変換では周波数特性を求める際に時間領域の情報は失われる
https://ja.wikipedia.org/wiki/%E3%82%A6%E3%82%A7%E3%83%BC%E3%83%96%E3%83%AC%E3%83%83%E3%83%88%E5%A4%89%E6%8F%9B

プログラムで扱うなら離散ウェーブレット変換
https://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%82%A6%E3%82%A7%E3%83%BC%E3%83%96%E3%83%AC%E3%83%83%E3%83%88%E5%A4%89%E6%8F%9B
2019/12/05(木) 07:07:45.12ID:MEu1VAiTM
確かにフーリエ解析では周波数成分の変化の時系列データを扱うのは難しい
少し浅はかだったなすまん
それにしても数学者が理論を確立して証明しそれをベースに開発が進むという典型例だな
484デフォルトの名無しさん (ｱｳｳｨﾌ FFa9-MVf8)
垢版 |
2019/12/05(木) 11:04:28.35ID:IbmhSLeWF
200年くらいかかってるな
ベイズで100年ちょっとか
485デフォルトの名無しさん (ｱｳｱｳｳｰ Saa9-uArc)
垢版 |
2019/12/05(木) 12:56:44.93ID:esMh+bxMa
>>480
さあ？まあ、実際にやってみな。自分でピアノやオルガンのキーを沖縄音階で適当に押すだけでわかる。
2019/12/05(木) 13:09:00.01ID:2uRKrxFid
自分で弾いたら曲になるように弾いちゃうからランダムじゃない
本当にランダムで弾いたら曲にならない
487デフォルトの名無しさん (ｱｳｳｨﾌ FFa9-MVf8)
垢版 |
2019/12/05(木) 13:51:21.95ID:IbmhSLeWF
ム板ならそれらしくランダムに演奏するソフトうｐ汁
https://www.youtube.com/watch?v=5dsFqZf8owg
2019/12/05(木) 15:14:54.84ID:2uRKrxFid
糞曲に興味はない
2019/12/05(木) 23:45:36.26ID:5h4sz8350
質問失礼いたします。
以下のpopcountは引数xを2進数で表したときの1の数を返す関数なのですが、
動作原理がよく理解できないため考え方のヒントなどをいただけないでしょうか。

int popcount(unsigned long long x)
{
　　x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
　　x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
　　return (int)(((x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f)) % 0xff);
}

以下のpopcount2は自分で作ったもので、これならうまくいくことは分かるのですが、
上のpopcountも本質的には同じことをやっていると考えていいものなのでしょうか。

int popcount2(unsigned long long x)
{
　　int n = 0;
　　for (int i = 0; i < 64; i++)
　　{
　　　　if ((x & 1ull << i) != 0ull)
　　　　{
　　　　　　n++;
　　　　}
　　}
　　return n;
}

どうぞよろしくお願いいたします。
2019/12/05(木) 23:51:53.81ID:rB1NeBwS0
https://ideone.com/8LfIh0
こんにちは。
ちょっと思いついたので、こういうコードを書いたのですが、
普段からreallocを使わないのでこのコードがあっているか解らないのです。
これで大丈夫ですか？
2019/12/06(金) 00:02:45.40ID:lGRN9wM80
>>490
reallocが成功した場合古いポインタに対してfreeは呼ばなくていいと思いますよ。
reallocの戻り値は古いポインタと異なるものになる保証はないはずなので、
freeを呼んでしまうとせっかくreallocした領域まで解放されてしまうかも。
2019/12/06(金) 00:04:45.19ID:j6TI2G0x0
>>491
了解です。ありがとうございました。
2019/12/06(金) 00:12:50.26ID:lGRN9wM80
>>492
ちゃんとコードを読んだら↓の部分はケアされてましたね。失礼しました。
> reallocの戻り値は古いポインタと異なるものになる保証はないはずなので、

ただ、reallocが成功したらfreeは呼ばなくていいのは間違いないと思います。
2019/12/06(金) 00:50:56.12ID:j6TI2G0x0
>>490 のreallocのコード返り値のポインタが不定を指しているので、使わないでください。
こっちを使ってください。
https://qiita.com/yakitori32/items/98256db666029fb5ebca
2019/12/06(金) 00:55:18.93ID:j6TI2G0x0
>>493
了解です。ありがとうございます。
2019/12/06(金) 01:07:01.79ID:Rsc9FZ2h0
>>489
超高速ビットカウント
でググって出てくるページでちゃんと解説してくれてる
この手のよく見るやつはちょっとググれば解説見つかる

何を本質と置くかによるけど両者はそもそもアルゴリズムが違うのでその観点からなら違う
どちらのコードも結果は同じでも前者のほうが圧倒的に処理速度が早い
ビット数などが必要になる処理では速度が重要になるケースも多々あるので結果が同じでも後者は使い物にならない場合もある
2019/12/06(金) 01:36:02.35ID:lGRN9wM80
>>496
レスありがとうございます。紹介していただいた記事を読ませていただき、大変勉強になりました。

ただ、>>489 の場合だと「ビットカウントするデータ列がある程度長い場合」には
当てはまらないため記事の前半の内容がアルゴリズムの基本になるとか思うのですが、
私が理解した範囲で記事の内容を参考にして関数を作成しても以下のようにしかできませんでした。

int popcount(unsigned long long x)
{
　　x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
　　x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
　　x = (x & 0x0f0f0f0f0f0f0f0f) + (x >> 4 & 0x0f0f0f0f0f0f0f0f);
　　x = (x & 0x00ff00ff00ff00ff) + (x >> 8 & 0x00ff00ff00ff00ff);
　　x = (x & 0x0000ffff0000ffff) + (x >> 16 & 0x0000ffff0000ffff);
　　return (int)((x & 0x00000000ffffffff) + (x >> 32 & 0x00000000ffffffff));
}

しかし >>489 の関数はこれを途中で打ち切って % 0xff をくっつけたような形になっており、
やはり完全な理解には至っていない状況です。
もし可能であれば、この部分についてもヒントをいただけると大変嬉しく思います。
たびたび申し訳ありませんが、どうぞよろしくお願いいたします。
2019/12/06(金) 04:41:11.15ID:hd4ipDIZM
>>497
64ビット長のビットカウントの最大値はたかだか64なので8ビット(最大255)で表現できる
一方、64ビットデータの分割統治による畳み込み計算は1回目で2ビット×32組、2回目で4ビット×16組、3回目で8ビット×8組の結果が得られる
ビット数を求めるだけなら3回目の結果が得られた時点で8ビットの最大数(255)で3回目の畳み込み結果の剰余を求めてやればそれぞれの組の重み(ビット数)が計算できる
(64を超えることはないことが明らかなので)
2019/12/06(金) 04:45:05.84ID:hd4ipDIZM
訂正
それぞれの組の重みの総計(ビット数)
2019/12/06(金) 05:11:25.02ID:lGRN9wM80
>>498
わかりやすいご説明どうもありがとうございます！ほぼ理解できたと思います。
たとえば十進数の123を十進数文字の最大値9で割った余りは
1+2+3と等しくなりますが、これと同じ原理ということですよね？

ただよくよく考えてみると、そもそも十進数の各桁の合計を9で割った余りが
元の数を9で割った余りと等しくなることについても
お恥ずかしながら豆知識として知っているだけで原理を理解できていませんでした。
ただこれに関してはもはやC言語ではなく算数の問題なので、
その方面の解説サイトをググって勉強しようと思います。
なにはともあれ、回答してくださった皆様方、どうもありがとうございました。


>>495
読みやすい記事を提供してくださっているので、もう少しだけコメントさせてください。

現状だと、MemoryReAllocateを呼び出す側は関数の成否を確認するために
Mem->Memoryを覚えておく必要がありますので、MemoryReAllocateの引数に
参照渡しを使われるならMemoryReAllocateの戻り値はMomeryではなくて
成否を表すboolなどにされてはいかがでしょうか。

また、reallocは第一引数としてNULLを許容しているので
MemoryReAllocateは入力のMem->MemoryがNULLであっても
Mem->ElementSizeが正しい値であれば正常に動作しますが、
その一方でMemoryAllocateは失敗するとElementSizeがゼロの構造体を
返すので少しアンバランスかなと思いました。

あと、MemoryFreeがboolを返すのであれば、freeの前にNULLチェックを入れて
その結果をMemoryFreeの戻り値としてもいいかなと思いました。
（free関数自体はNULLを渡しても何もしないだけで問題は起こりませんが）

以上お目汚し失礼しました
2019/12/06(金) 05:15:04.10ID:PFBD6caPd
1回進むごとに
2bitずつに区切って、1の数を各2bitに入れる
4bitずつに区切って、1の数を各4bitに入れる
8bitずつに区切って、1の数を各8bitに入れる
...

となるので
>>489だと各バイトの1の合計が、各バイトに入る

各バイトなので256バイトのテーブルを使う方法もある
チープなCPUだとこちらの方が速い

逆にリッチなCPUだと数える命令が最初から備わってたりするしベクタ化も可能

Icelake以降だとAVX512VBMIの命令を使って
超高速に64バイト分カウント出来る
2019/12/06(金) 05:24:05.53ID:PFBD6caPd
>>500前半
なんか違う

10進数の各桁に関しては
1000a+100b+10c+d
=999a+99b+9c+a+b+c+d
=9(111a+11b+c)+(a+b+c+d)

これを2進数でやると
9のところが1になるからあまり意味がない
2019/12/06(金) 05:33:31.46ID:PFBD6caPd
分割統治っていうより
レジスタ内の桁数を使ってSIMD演算してるって感じ

01020304 + 02040608

2桁ずつの4個の足し算になってるでしょ？
2019/12/06(金) 05:47:57.81ID:PFBD6caPd
vpsrld
vpermb
vpermb
vpaddb

AVX512VBMIを使うと
レジスタに値がある状態で
4命令で64バイト分
2019/12/06(金) 05:56:22.53ID:lGRN9wM80
>>501 >>504
レスありがとうございます。

> 各バイトなので256バイトのテーブルを使う方法もある
確かにある程度のビット幅ごとにテーブルを使って計算する方法は
シンプルですが効果が高そうですね。

> 逆にリッチなCPUだと数える命令が最初から備わってたりするしベクタ化も可能
> 4命令で64バイト分
勉強になります。本当に速さが必要ならCPU自体の理解から始めるべきなんですね。
このあたりのハードウェアの違いは標準ライブラリ関数が吸収してくれると最高なのですがｗ


>>502
10進数の話の数式どうもありがとうございます！大変勉強になりました。

そうすると、>>489 の popcount の最後にやっているのは
2進数というか0x100進数で、

0x1000000*a+0x10000f*b+0x100*c+d
=0xffffff*a+0xffff*b+0xff*c+a+b+c+d
=0xff*(0x01010x*a+0x0101*b+c)+(a+b+c+d)

ということになると思うのですがいかがでしょうか。
2019/12/06(金) 05:58:37.54ID:lGRN9wM80
>>505 の数式が変でした。正しくは以下のとおりです。失礼しました。

0x1000000*a+0x10000*b+0x100*c+d
=0xffffff*a+0xffff*b+0xff*c+a+b+c+d
=0xff*(0x010101x*a+0x0101*b+c)+(a+b+c+d)
2019/12/06(金) 06:20:08.91ID:PFBD6caPd
最後の % 0xff を見てなかった
なので各バイトの1の個数と勘違いしてました

>>506はその通り

%は、除算命令を使うと遅いので
コンパイラは
0x0101010101010101
との乗算とシフトに置き換えそうです

PCの64bit環境だとPOPCNT命令がそのまま1命令
Icelake以降だとVPOPCNTQで8個を1命令
で出来ます
2019/12/06(金) 06:24:24.02ID:PFBD6caPd
x % 0xff
よりは
x * 0x0101010101010101 >> 56 & 0xff
の方が直接的でコンパイラを頼らない記述でしょう
2019/12/06(金) 06:34:20.70ID:hd4ipDIZM
それだと
剰余 x % 0xff
ではなくて
商 x / 0xff
2019/12/06(金) 06:36:33.62ID:PFBD6caPd
>>508 で大丈夫
乗算の筆算を考えてみよう
2019/12/06(金) 06:37:31.16ID:lGRN9wM80
>>507-508
レスありがとうございます。

> x % 0xff
> よりは
> x * 0x0101010101010101 >> 56 & 0xff
> の方が直接的でコンパイラを頼らない記述でしょう
コンパイラの最適化によって一行目が三行目に
置き換えられる可能性があるということですか！？
難しそうですがちょっと考えてみたいと思います。

> PCの64bit環境だとPOPCNT命令がそのまま1命令
> Icelake以降だとVPOPCNTQで8個を1命令
本当に速度を求めるならCPUの命令を直接使えということですね。
覚えておきます。
2019/12/06(金) 06:42:08.81ID:PFBD6caPd
>>511
コンパイラは普通、定数の除算は乗算に置き換えます
乗算、シフトは1クロック、除算は数十クロックかかるのが普通なので

ただ、
>>508 にまでは最適化されないかも
なので>>508の方が良いです
2019/12/06(金) 06:54:43.75ID:lGRN9wM80
>>512
ありがとうございます。そのようにしたいと思います。

ご親切に甘えてしまい申し訳ないのですが、
もう一つ質問させてください。今、
① = x % 0xff
と
② = x * 0x0101010101010101 >> 56 & 0xff
について考えていたのですが、
x = 0xff のとき、
① = 0x00, ② = 0xffのように、別の値になりませんか？
これは、どこか書き間違いがあるとういことでしょうか。
それとも、この違いは今回の用途では問題にならないということでしょうか。
2019/12/06(金) 06:57:32.55ID:lGRN9wM80
>>512
立て続けにすみません。。。たった今理解しました。
「この違いは今回の用途では問題にならない」が正解ですね。
2019/12/06(金) 06:57:55.91ID:PFBD6caPd
除算命令、
Skylakeで最大90クロックだそうで...
簡単な命令だと1クロックで3～4個実行出来る事を考えると劇遅ですね

Icelakeだと18クロックなので
改善されてるみたい
2019/12/06(金) 07:06:52.23ID:lGRN9wM80
>>515
> 除算命令、
> Skylakeで最大90クロックだそうで...
なんと！しかも、「最大」という表現が付くんですね。
つまり、ただの数値計算なのに
クロックの数がデータに依存する可能があるということ…？
2019/12/06(金) 07:12:58.28ID:PFBD6caPd
>>516
除算命令の実行時間はデータに依存します
内部的にループしてるようなものなので

SIMDの除算は多分一定
Icelakeももしかしたら一定かもしれません

SIMD乗算も非常に小さな値だと遅い事があったような
2019/12/06(金) 07:35:33.29ID:lGRN9wM80
>>517
小さい値だと遅い！？
すみません、ハードウェアの知識がなさすぎて
タイプミスをされたのか本当にそうなのかの判断すらつかないです。。。
2019/12/06(金) 07:55:08.53ID:DDupnuWl0
https://ja.m.wikipedia.org/wiki/%E9%9D%9E%E6%AD%A3%E8%A6%8F%E5%8C%96%E6%95%B0

ここの｢性能問題｣参照
浮動小数点演算の話ですので今回は関係ないです
2019/12/06(金) 07:59:35.87ID:/1U5BHO/0
そりゃ並列処理できるような相互依存性の低い大量のデータでもあるならともかく
小さなデータ塊対象だとパック化やアンパック化する手間が掛かる分だけ
総合的にはSIMD使った方が遅くなるだろ
馬鹿となんとかは使いようと言うだろ
2019/12/06(金) 08:10:43.32ID:DDupnuWl0
どこの誤爆か気になる
2019/12/06(金) 12:19:42.67ID:PPEOwhLkd
>>520
馬鹿がSIMD使うと遅くなる
それはそうかも
2019/12/06(金) 15:17:31.13ID:lGRN9wM80
>>519
勉強になります。
非正規化数という言葉はちらっと聞いたことはありますが、こういうデメリットもあるんですね。
そして、それでも非正規化数を使うのは
「浮動小数点数の加減算は決して『アンダーフローによるゼロ』にならない」
という理由があるのだということも初めて知り、とても興味深く感じました。


ところで、ビット演算に関してもう一つ相談させていただいてもよろしいでしょうか。

動的メモリ再確保のコストを減らすために確保するメモリのサイズを必ず 2ⁿ-1 の形にしたくて、
与えられた数を下回らない最小の 2ⁿ-1 の値の値を返すような関数を作って使っています。
つまり引数xを2進数で表したときの一番上位の1以下をすべて1に置き換えるような関数で、
具体的には以下のように記述しています。

int fill_lower_bits(int x)
{
　　x |= x >> 1;
　　x |= x >> 2;
　　x |= x >> 4;
　　x |= x >> 8;
　　x |= x >> 16;
　　return x;
}

この関数は割と使用頻度が高いので、PCの64bit環境にPOPCNT命令があるように、
もしfill_lower_bitsと似た振る舞いをする命令があれば名前を教えていただけないでしょうか。

（続く）
2019/12/06(金) 15:18:25.28ID:lGRN9wM80
（続き）
また、こちらはあまり使い道は思いつきませんが、

int fill_higher_bits(int x)
{
　　x |= x << 1;
　　x |= x << 2;
　　x |= x << 4;
　　x |= x << 8;
　　x |= x << 16;
　　return x;
}

という関数を考えることもできて、これなら

int fill_higher_bits(int x)
{
　　return -(x & -x);
}

のように簡単な書き方に変更できます。
fill_lower_bitsについてもこういうテクニックがあればいいなと思っているのですが、
もし何かご存知であれば教えていただけると嬉しいです。
2019/12/06(金) 19:09:08.62ID:PPEOwhLkd
>>523
BSR命令といくつかの命令を組み合わせて出来ます
Cからだと _BitScanReverse64

>>524
x | -x
の方が良いと思います
2019/12/06(金) 19:33:49.52ID:lGRN9wM80
>>525
何度も本当にどうもありがとうございます。大変勉強になります。

> _BitScanReverse64
こんな命令があったとは！
この名前で検索したら、今まで知らなかった興味深いページがたくさんヒットしました。
ReverseじゃなくてForwardというのもあるみたいですが、
Forwardの方はマイナスを使う方法でも十分高速になりそうなので、
どちらが速いか検証してみようと思います。

> x | -x
確かに…。
ド・モルガンの法則で ~(x & ~x) が ~x & x に書き換えられるのはすぐに分かるのですが、
もしかしてそれと同じことがマイナスでもできるのでしょうか。
-x が ~x + 1 と同じになることは理解しているので、ちょっと考えてみたいと思います。
2019/12/06(金) 19:53:04.32ID:lGRN9wM80
>>526
> ド・モルガンの法則

-(a & b) = -a | -b が成り立つかなと期待したのですが、
a = 0, b = 1 のときにつまずいてしまいました。

でも、>>525 に書いていただいた -(x & -x) = -x | x は間違いなさそうです。

こういう式の変形って、どこかテキストに載っていたりするのでしょうか。
2019/12/06(金) 20:51:24.53ID:DDupnuWl0
自分で頑張って探すんです

~x
x-1
-x
&
|
^

これらを組み合わせれば
一番右のビット関連がいろいろと出来ます

???10000
に対して
11110000
11100000
00010000
00011111
00001111
これらを得る最小回数の演算を考えてみてください
2019/12/06(金) 21:03:52.43ID:vzfmAUcv0
ド・モルガンと似た問題で、
「君たち2人は注意されないならば、君たち2人は私語を止めない」
の対偶、
「君たち2人が私語を止めるならば、君たち2人は注意される」
って矛盾にちょっと考えてしまったわ。
2019/12/06(金) 21:07:30.59ID:BprTHIND0
x 注意される
o 注意された
2019/12/06(金) 21:15:00.21ID:vzfmAUcv0
>>530
さすが、その通り。
2019/12/06(金) 23:44:25.67ID:DDupnuWl0
>>523
メモリ確保やアクセスの時間に比べれば
サイズ計算の時間は無視出来る

ビット演算の趣味として楽しむ分には良いけど
普通にループでもパフォーマンスは変わらない

パフォーマンスが重要じゃないところ
(つまりほとんどの部分)は
移植性、見やすさ、工数、...
などが優先される

ということは知っておいた方が良いですね
2019/12/06(金) 23:51:44.77ID:Rsc9FZ2h0
分野によってはループや比較による分岐は遅すぎて使えないなんてことままあるよ
2019/12/07(土) 00:10:26.85ID:n8phrA6e0
>>523の話
2019/12/07(土) 00:10:27.55ID:4NjUP+TJM
それは経験談？
それとも誰かからの受け売り？
2019/12/07(土) 00:15:02.34ID:n8phrA6e0
動的メモリ再確保
のサイズ計算の話

オーダーnに対して係数の小さなオーダーlog nは無視して良い
って話
2019/12/07(土) 01:14:15.17ID:kGPNKNyL0
ちょっと前にスレで騒がれていたフーリエ変換に関する話題

50年来の信号処理に関する謎が解かれる、逆高速フーリエ変換がついに一般化
https://fabcross.jp/news/2019/20191206_fast-fourier-transform.html
538デフォルトの名無しさん (ｴﾑｿﾞﾈ FF43-MVf8)
垢版 |
2019/12/07(土) 19:02:43.91ID:Tn5G8ZSlF
解明って言うんか？これ
2019/12/14(土) 01:27:42.96ID:TU6i1yGkx
C言語というか、WindowsのCですが、
たとえば strcpyの lstrcpyと _tcscpyの違いは何なのでしょうか
前者は WindowsAPI、後者は VC++CRTという説明を見たのですがよくわからないのです
両者とも UNICODE(後者は_UNICODE) の有無で charとwchar_tを切り替えるようですが、どちらをどんな時に使用するのかが分かりません。
2019/12/14(土) 10:20:34.10ID:00Pm6Tju0
crtへの依存を減らせる分、常にlstrcpyを使えばいいと思うよ。lstrcpyは不正アクセスしたときに例外投げてくれるみたいだし。
自分なら依存減らす＆安全性のためにstrncpyとwcsncpyを選ぶけど
2019/12/14(土) 23:23:03.56ID:ECY2395Ex
>>540
ありがとうございます。
539です。

今後は気をつけようと思いますが、過去に書いたコードは何ともいたし難く…orz
なぜ先に lstrcpyを見つけなかった 2014年のオレ…

でも、内容が古いのかもしれませんが、ある記事によると CRTの依存を断ち切るのも容易ではないようで。。。
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。