C言語なら俺に聞け 152

2019/06/17(月) 18:27:10.41

!extend:checked:vvvvv:1000:512
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言語なら俺に聞け 151
https://mevius.5ch.net/test/read.cgi/tech/1554171817/

VIPQ2_EXTDAT: checked:vvvvv:1000:512:----: EXT was configured

2019/07/24(水) 12:43:12.82

>>720
Z80やx86にはBCD関連の命令がありました。

最近のレジスタビット数の大きいプロセッサは知りませんので伺いました。

10で割った余りだと桁数nとしてO(n^2)の計算量になりますよね。
流石にそれはないかなと思っています。

2019/07/24(水) 12:53:46.86

https://days-of-programming.blogspot.com/2016/01/picbcd.html?m=1

2019/07/24(水) 13:07:48.35

O(n)じゃないか？
x64はもう命令ないんだね

2019/07/24(水) 13:17:22.40

O(n)だね。
文字列変換時にBCDにするのではなく演算からBCDとして扱うプログラムを見たことある。
あまり効率が良いとは思えなかったが。

2019/07/24(水) 17:12:57.35

x64の場合、ALUでやる2ケタの加減乗除の方は廃止だが、FPUでやる18ケタの10進と2進の間の変換はまだ使える

2019/07/24(水) 17:15:31.56

聞くのはここでいいのか微妙だけど質問です
abzのエンコーダで回転方向を検知したいんですがzパルスでリセットされるときに回転方向が正しく検知されなくなってしまうところの解決方法どなたか知ってますか

2019/07/24(水) 17:21:50.17

>>728
mod 10でO(n)、
それを桁数nに比例した分繰り返すからO(n^2)
と考えています。

O(n)で内部2進表現の整数→10進数の文字列に変換ができればいいのですけどね。

あるいはdecimal型を持つ言語がありますが、そのような型では内部でBCDで持ってたりするのでしょうか。

2019/07/24(水) 17:55:29.62

1桁分のmod 10だけなら計算量は固定なのでO(1)
n桁分を繰り返すなら計算量はO(n)
すべての計算量のオーダーとしてはO(n)

2019/07/24(水) 18:22:37.58

>>733
わかりました。
剰余を固定命令数でできる桁数内であればO(n)でできるということですね。

現在、内部2進表現の整数を10進数の文字列に変換する方法としては、mod 10の繰り返しがメジャー(ベスト)ですか？

printfの%dもこの実装が主流でしょうか。

2019/07/24(水) 18:23:32.53

modの計算量が固定ってこともないんじゃ？
除数にかなり依存しそうな

◆QZaw55cn4c (ﾜｯﾁｮｲ 3f47-19w1) · 2019/07/24(水) 19:18:26.26

>>718
そうです、10進法変換は表示のときにはじめて実施します

◆QZaw55cn4c (ﾜｯﾁｮｲ 3f47-19w1) · 2019/07/24(水) 19:20:00.24

>>719
単純に 10 で割った余りを並べるだけですが、ただ >>717 で紹介したコードでは幾分かの最適化が追加されています

◆QZaw55cn4c (ﾜｯﾁｮｲ 3f47-19w1) · 2019/07/24(水) 19:21:21.51

>>726
いや、10　で割った余りそのものであり、他に方法はありません
ただ、最適化の余地はあり、それは >>717 に示しました

◆QZaw55cn4c (ﾜｯﾁｮｲ 3f47-19w1) · 2019/07/24(水) 19:22:41.56

>>729
BCD はインプリメントする側としてはやる気が起きないものだ、と思いますよ
足し算、引き算はいいとして、掛け算、割り算は BCD では実装できないのです

◆QZaw55cn4c (ﾜｯﾁｮｲ 3f47-19w1) · 2019/07/24(水) 19:23:34.46

>>734
＞現在、内部2進表現の整数を10進数の文字列に変換する方法としては、mod 10の繰り返しがメジャー(ベスト)ですか？

他に方法はありません、ただし最適化する余地はあると思っています

2019/07/24(水) 21:42:02.70

>>739
は？　乗算と除算が実装できない？？
俺らの脳には義務教育できっちり実装されているんだがｗ

◆QZaw55cn4c (ﾜｯﾁｮｲ 3f47-19w1) · 2019/07/24(水) 21:53:50.78

>>741
今の話題は BCD
BCD にて効率的に乗算・除算を実装している CPU はありますか？

2019/07/24(水) 23:16:58.12

>>737
わかりました。
10進全桁を一旦BCDで全て求めなくても、
10進1桁ずつ求めることが出来るのですね。

>>738
単純に興味があるのでお聞きするのですが
「他に方法はありません」と断定する理由は何でしょうか。

効率を考えなければ、
単なる最適化ではない異なるアルゴリズムの他の方法が
容易に思いつきますが、例えば、
10で割る方法が原理的に最適であると証明できる
というようなことでしょうか。

2019/07/24(水) 23:55:14.64

秘密はvoidにありそう

2019/07/25(木) 00:31:43.06

DIVやIDIVを上回る何かを見つけたとしたら大ごとですやん
除算器のない初期のRISCや貧ソな何かで無理矢理だとシフト使こた工夫もアリかもしれんけど
if (x<0) {x = !x; ...}
do {x = x>>4 +(v = t = (x&0xf), t>>=2, t &= (t>>1), v -= t*10, t);...}while (x)
みたいな？

2019/07/25(木) 00:55:04.35

あ、2 と 4 で or 取らなきゃダメか

2019/07/25(木) 01:12:42.13

テーブル探す様な方法はないの？

◆QZaw55cn4c (ﾜｯﾁｮｲ aa47-UOPh) · 2019/07/25(木) 05:20:17.48

>>747
なるほど…そういう方向性はありえますね

2019/07/25(木) 06:55:37.49

>>742
そう、BCDの話だ
おまえさんはBCDでは乗算と除算が実装できないと言ったんだ
マイクロコードかどうかは関係ない

2019/07/25(木) 10:19:57.39

>>747
あなんか昔はそういうHWがあったらしい

2019/07/25(木) 10:24:34.16

乗算部分はテーブル化しやすそう
除算は何処で軽くするのがいいのか皆目見当がつかねぇ

2019/07/25(木) 10:39:38.12

10進表記に関しては、いきなり割り算するよりはまず9とか99とか999とか9999とかと引き算なり大小比較なりしてもよさそうだけども。

2019/07/25(木) 10:43:55.98

まあ除算は昔からクソ遅いよな
floatで逆数かける感じの方が速そうだ

2019/07/25(木) 10:50:12.92

>>753
可能なら逆数を掛けたほうが早いなんてハックに効き覚えがある
(同じように2,4,8はシフト演算子で処理)

2019/07/25(木) 12:08:29.39

ビットリバーサルについて質問です
誰もがわかりやすく簡単にできる方法は
C言語でどうなるでしょうか？

2019/07/25(木) 12:33:12.38

>>753-754
初期のスーパーコンピューターCray-1はそういう構造
って結構有名な話
https://news.mynavi.jp/article/architecture-389:amp/

2019/07/25(木) 12:35:03.65

整数定数除算は速度優先オプティマイズでアセンブラ出力見てみなよ

2019/07/25(木) 12:53:26.79

>>734
隣同士でひっくり返して、2こセットで隣同士でひっくり返して、4こセットで隣同士でひっくり返して…
ってやるらしい。賢いね
uint32_t reverse(uint32_t x) {
x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
return ((x >> 16) | (x << 16));
}

2019/07/25(木) 12:55:25.80

おっと>>755の間違い

2019/07/25(木) 13:08:04.63

>>755
簡単でわかり易いと言うなら素直にビット毎に処理すればいいと思う
unsigned int x = …;
unsigned int y = 0;
for(size_t i = 0; i < 32; i++){
y <<= 1;
y |= x & 1;
x >>= 1;
}
てな感じ
高速化したいならテーブル引くなりすればいいかと

2019/07/25(木) 13:31:47.50

>>758
>>760
ありがとうございます
どちらともわかりやすいですね！

2019/07/25(木) 13:33:38.69

高速フーリエ変換でのビットリバーサルの書き方がどんなものがあるのか興味があったのでききました

ビットリバーサルでの処理では速度は余り変わらそうなのでわかりやすい

表記で書こうとおもいます

◆QZaw55cn4c (ﾜｯﾁｮｲ aa47-UOPh) · 2019/07/25(木) 19:25:45.50

>>749
では訂正しましょう
「BCD では『効率的な』乗算・除算は実装できない」、てへぺろ

◆QZaw55cn4c (ﾜｯﾁｮｲ aa47-UOPh) · 2019/07/25(木) 19:26:49.53

>>754
その逆数を実時間で効率的に求める方法はありますかね…あらかじめ求めておくというのは除いたとして

2019/07/25(木) 20:09:17.88

BCDじゃなく10bitで10進3桁表すieee 754-2008のdecimal floating pointだと、回路的にそこまで無駄じゃないよね

2019/07/25(木) 20:28:09.79

>>764
ニュートン法とか？

2019/07/25(木) 20:40:39.43

>>763
効率的とは？
ハードワイヤードでも組めるだろ？

2019/07/25(木) 20:56:17.18

加算　減算　乗算　除算　って回路的にどうやってるんだ？
マルチバイブレータ系の回路が基本になってるのはわかるけど
詳細部でどうやってるんだ？

2019/07/25(木) 21:14:22.23

log通った後だと　乗算が加算に　除算が減算になるけど
log通して加減算した後に累乗で戻すほうが重いんじゃろな

2019/07/25(木) 21:23:45.17

>>768
加減算はXORそのもの。
乗除は知らん。

2019/07/25(木) 21:49:16.57

>>770
加減算のXORの場合　繰り上がりはどうやってるんだ？

2019/07/25(木) 22:44:02.09

>>771
単なるANDだろ
https://ja.m.wikipedia.org/wiki/加算器

2019/07/25(木) 22:52:27.40

繰り上がりはand
ただ実際は一気にがばっと先読みするので、すぐ下の桁だけに依存するわけではない

2019/07/25(木) 23:15:13.43

お前らコンピュータアーキテクチャの勉強もしたことないのか？

2019/07/25(木) 23:18:36.17

ビジコン嶋さんがアップをはじめました

2019/07/26(金) 00:14:46.69

>>772
https://ja.wikipedia.org/wiki/%E5%8A%A0%E7%AE%97%E5%99%A8
半加算器と全加算器の組み合わせとかいろいろあるんやなｗ

2019/07/26(金) 00:22:06.93

キャリールックアヘッドアダー　っていう加算器の高速化手法もあるんかぁｗ

◆QZaw55cn4c (ﾜｯﾁｮｲ aa47-UOPh) · 2019/07/26(金) 08:11:37.04

>>777
実はリップルキャリーと回路は同じです
キャリールックアヘッドは、「多入力ゲートは2入力ゲートを組み合わせた分よりも速い」という仮定のもとに組まれたものです

2019/07/26(金) 08:36:36.41

またまたいい加減なことを。
2入力ゲートだけでCLA作れるし、2入力ゲートだけのRCAより速いよ。

2019/07/26(金) 09:14:13.64

そりゃ多入力ゲートが2入力で模倣できるって言ってるだけでは

2019/07/26(金) 09:22:46.42

同じ入力数に制約しても速いって言ってんの

2019/07/26(金) 10:49:53.96

マルチエミッタって、スイッチング速いんだっけ？

2019/07/26(金) 13:02:58.65

スレチですみません
ここの人達は「プログラム」と聞いたときにどちらを思い浮かべますか？

* バイナリ
* コードが書かれたファイル
* コード

2019/07/26(金) 13:05:55.53

ROMにプログラム（書込）するのはバイナリ

2019/07/26(金) 13:08:13.51

>>784
やはりバイナリですよね
プログラム＝バイナリという理解で合ってますよね

2019/07/26(金) 13:18:25.37

はい
あなたの考えは一切の曇り無く隅々まで正しいです
なのであなたの理解が最も正しいです
それについてわたくしどもは一切口出しすべきことはございません

あなたこそが正しいです

2019/07/26(金) 13:27:35.81

>>786
しかし辞書にはプログラムは問題解決の手順を特定の言語書いたものとあったので、
そう考えるとプログラムはバイナリを内包するという捉え方の方が正しいですよね
あと>>784さんはプログラムを動詞として使ってますが、それも使い方としては一般的なんですよね

プログラミングは10年以上やっているんですが、いまさらになってプログラムの意味を調べていて……
プログラムの意味をなんとなく理解してたのがわかって、こんな質問してしまってるんですが

2019/07/26(金) 13:36:27.21

>>787
どうやら貴方はプログラムより先に国語を勉強したほうが良いようだ。

2019/07/26(金) 13:37:37.41

ンなことカンケーなしに「俺はこう思ってる」「正解をくれ」を最初の>>783に書けばいいじゃん
なんでお前のお気持ちを察しなきゃいけないワケ
後出しジャンケンのコミュニケーション不全の物体だからマンセー要員しか求めてない

「どちらを思い浮かべますか？」と聞いてるんだから、
オレが思い浮かべるだけなら正解も不正解もない、
なのにいきなり「合ってる」とか言いだすとと値踏みされてるから不快だ

なんでお前なんかに正誤判定されなきゃいけないの
正解を求めている旨を最初>>783に書いてないからコミュニケーション不全だ

一見自由そうに見えるアンケートを取っておいて、それが合格か不合格かテメー独自のお気持ちで決めて人間を値踏みする、
その思考経路がアレすぎ

2019/07/26(金) 13:43:27.73

アンケート取ったのはどっちが一般的なのか知りたかったからですよ
そんなにカッカしないでください

一般的かどうかに私の主観は関係ないでしょ？

2019/07/26(金) 13:44:53.75

一連の処理(命令)を書いたものがプログラムだろ
それを書く作業がプログラミングだろ
何が疑問なのかよくわからん

2019/07/26(金) 13:48:17.76

>>783
テレビ番組表

2019/07/26(金) 13:59:21.82

>>791
そうなんですが、プログラムって言葉がけっこう色んな意味で使われていて、調べていると混乱するんですよね……

2019/07/26(金) 13:59:36.19

>>789
同感

辞書って言われて正直少しムッとした
ちなみに俺はその手の辞書サイトの間違いを指摘して訂正させたことがある

2019/07/26(金) 14:09:18.87

>>793
ITの分野で>>791以外の意味で使われることある?

2019/07/26(金) 14:20:35.08

>>794
別にここの人達の知識を疑ってるわけじゃないです
あと試すようなこともしてるつもりはないです

>>795
たとえばバイナリを指してプログラムと言うじゃないですか
あとアプリのこともプログラムと言いますし
プログラミングのことをプログラムするとも言うし

バイナリもアプリも「一連の処理(命令)を書いたもの」とすることはできますが、
なんか混乱するんです

2019/07/26(金) 14:22:29.61

あとプログラムとコードの違いもよくわかりません
コードだって命令を書いたものじゃないですか
それだとプログラム＝コードということになりませんか？

2019/07/26(金) 14:34:16.48

>>796
voidに秘密がありそうですよ

2019/07/26(金) 14:39:22.98

>>798
「プログラミング=プログラムを作ること」なら、日本語の命令を書くことはプログラミングなのかという疑問が生まれませんか？
人間に与える日本語の命令を書いた場合、それはプログラミングと言えるのでしょうか？

2019/07/26(金) 14:41:27.15

バイナリもアプリもソースコードもプログラムを内包するってことだろ

2019/07/26(金) 14:45:23.07

IT分野の話じゃないならスレチもいいとこだな
そんなの辞書引けば分かるだろ

2019/07/26(金) 14:49:00.72

>>796
再びムッとしたぞ
人にものを尋ねておいて何だその態度は
失言ではなく性格のようだな

2019/07/26(金) 14:51:29.48

verilogはなんとプログラミング言語ではない

2019/07/26(金) 14:59:57.10

>>778
単純なマルチバイブレータ連結のカウンタ回路考えたら
段数が多くなるほど速度が遅くなるのは当たり前だもんね！

2019/07/26(金) 15:15:37.98

CPUの立場では、メモリ上に展開されている機械語のバイナリ列がプログラム
OSの立場では、実行ファイルがプログラム
C言語で記述する人にとっては、ソースファイル(郡)がプログラム

どのレイヤーの話かで意味が変わってくる可能性

2019/07/26(金) 15:15:43.78

ムッとしたってちょっと可愛い

2019/07/26(金) 15:18:34.64

機械にとっては機械語だけで充分なのに
人間の理解にとって高級言語は必要最低限

認識のちがいとか感受性　によって見方はかわるんかな？ｗ

2019/07/26(金) 15:25:46.61

用語なんて初めて使われた時の意味、定義化された時の意味、実際に使われてる場面での意味、
全部違ってることなんてザラでしょ。

2019/07/26(金) 15:56:34.19

>>806
わざとやってるんだよ
別にケンカがしたいわけじゃないから

2019/07/26(金) 15:56:40.90

>>782
スイッチング特性ってどうなんだろ？
トランジスタのｆｔに依存するんやない？

最近のトランジスタは1815なんかにくらべると桁がだいぶ違うｗ

2019/07/26(金) 17:11:28.14

>>799
言える。これだもの。

プログラム（program）
［名］(スル)
１ある物事の進行状態についての計画や予定。予定表。「新人教育のプログラム」
２演劇・映画・音楽会・テレビなどの演目・曲目・番組。また、出演者の紹介、解説などを印刷した小冊子や番組表。「雨天によりプログラムが一部変更された」
３コンピューターへ指示する、計算や仕事の手順を特定の言語や形式で書いたもの。また、それを作ること。

2019/07/26(金) 17:16:39.70

更に、日本語のコンピュータ用のプログラムというのもある。
昔々のピュータのBASICだとか、C言語でも関数名や変数名その他に漢字使えるのあったし、Javaとかでも識別子に漢字使えるし。

2019/07/26(金) 17:19:19.65

あ、ピュータじゃなくてぴゅう太だな。
https://ja.m.wikipedia.org/wiki/%E3%81%B4%E3%82%85%E3%81%86%E5%A4%AA

2019/07/26(金) 17:44:43.58

utf8が普及して、今の方がむしろ普通に日本語使えるようになったと思うよ

2019/07/26(金) 18:04:58.65

だな、今時メジャーな環境で識別子に漢字とか使えない方が珍しい

2019/07/26(金) 18:20:14.54

絵文字が普及して外人の作るプログラムがマルチバイト文字に完全に対応してきた
それまでは結構ダメダメだった

2019/07/26(金) 20:18:37.20

識別子に漢字使えるのにスペースは全角だとコンパイルエラーなのがちょっと納得いかない

2019/07/26(金) 20:49:01.65

0xE38080がUTFのスペース
0x20 がアスキーコード

いまやってみたら全然ちがうやんかｗ　　

2019/07/26(金) 20:51:55.69

>>797
言葉の意味は文脈で異なる。
ある言葉と別の言葉の関係は一致か不一致かだけでなく、包含したり一部のみ重複したりもする。

◆QZaw55cn4c (ﾜｯﾁｮｲ aa47-UOPh) · 2019/07/26(金) 21:21:44.32

>>779
＞2入力ゲートだけでCLA作れるし
そんなことをしたら「素子数ばかり馬鹿みたいに食らって速度はリップルキャリーと同一の遅さ」で、なんのためのキャリールックアヘッドなのかわからない、という悲惨な結果になりませんか？

◆QZaw55cn4c (ﾜｯﾁｮｲ aa47-UOPh) · 2019/07/26(金) 21:22:53.46

>>781
ありえないですね、キャリールックアヘッドは多入力で速度を稼ぐやりかたですよ、2入力に制限したらリップルキャリーと全然かわらないじゃないですか？

2019/07/26(金) 21:24:29.66

キャッシュの容量とかパイプラインのちょうどいい区切りとか
まで考えてプログラミングなんてはっきり言ってやってませんｗ
手抜きでしょうか？

2019/07/26(金) 21:50:39.91

演算器の設計 - 加算器(Adder)
https://news.mynavi.jp/article/computer_architecture-70/

演算器の設計 - キャリールックアヘッドアダー(1)
https://news.mynavi.jp/article/computer_architecture-71/

演算器の設計 - キャリールックアヘッドアダー(2)
https://news.mynavi.jp/article/computer_architecture-72/

パラレルプリフィックスアダー
https://news.mynavi.jp/article/architecture-73/

パラレルプリフィックスアダー(2)
https://news.mynavi.jp/article/architecture-74/

パラレルプリフィックスアダー(3)
https://news.mynavi.jp/article/architecture-75/

Lingアダー
https://news.mynavi.jp/article/architecture-76/

アダーの実装に関して
https://news.mynavi.jp/article/architecture-77/

2019/07/26(金) 22:01:03.66

>>821
いや、文字通り先読みが本質だと思いますよ
ゲートはいくつあってもいい

◆QZaw55cn4c (ﾜｯﾁｮｲ aa47-UOPh) · 2019/07/26(金) 22:10:45.70

>>824
＞文字通り先読みが本質だと思いますよ
薄っぺらい理解ですね
3 bit, 4 bit なりのアッダーを決めて、その MSB の和を作るのに必要な入力をじっと眺めて本質をつかんでください
単なる先読みではありませんよ

＞ゲートはいくつあってもいい
速くなるならね
でも 2 入力論理演算だけで作ったキャリールックアヘッドは速くならない…

2019/07/26(金) 22:18:01.82

>>825
そら、速い方がいいし回路もシンプルな方がいいですよ。
しかし、桁上がりを待ってるのと同じではないでしょうて。たとえ2入力ゲートを使ったとしても。