C++相談室 part146

**デフォルトの名無しさん** · 2019/11/07(木) 11:35:36.76

C++に関する質問やら話題やらはこちらへどうぞ。
ただし質問の前にはFAQに一通り目を通してください。
IDE (VC++など)などの使い方の質問はその開発環境のスレにお願いします。

前スレ
C++相談室 part145
http://mevius.5ch.net/test/read.cgi/tech/1568362404/

このスレもよろしくね。
【初心者歓迎】C/C++室 Ver.105【環境依存OK】
http://mevius.5ch.net/test/read.cgi/tech/1556142878/

■長いソースを貼るときはここへ。■
　http://codepad.org/
　https://ideone.com/

[C++ FAQ]
https://isocpp.org/wiki/faq/
http://www.bohyoh.com/CandCPP/FAQ/ (日本語)

**デフォルトの名無しさん** · 2019/11/26(火) 17:39:44.76

>>211
>>203

**デフォルトの名無しさん** · 2019/11/26(火) 17:59:37.88

いやそもそも>>195の前半で解答は終わってるだろ
>>195の後半は余計

**デフォルトの名無しさん** · 2019/11/26(火) 18:06:10.26

>>210
普通の型なら普通にC++で書いた方が良い
定数ならコンパイラが工夫する

普通じゃない型、例えば多倍長でも
1ビットずつシフトして速くなることは無いと思って良い

**デフォルトの名無しさん** · 2019/11/26(火) 18:06:14.04

>>210
＞今の技術使ったら爆速に
ならねーよw

**デフォルトの名無しさん** · 2019/11/26(火) 18:52:42.91

>>217
ならないかー。
コンパイルタイム時に置き換えるから、1サイクルに落ちるものだと・・・。

**デフォルトの名無しさん** · 2019/11/26(火) 19:27:14.09

爆速にならなくても1サイクルだろうよ

**デフォルトの名無しさん** · 2019/11/26(火) 19:41:24.45

1サイクルじゃシフトしか出来ない

**デフォルトの名無しさん** · 2019/11/26(火) 19:48:34.46

なんか根本的にconstexprを勘違いしてる初心者がよくそういうこと言うけど
定数同士の計算の省略なんか大昔からある最適化だぞ
C++03以前を偉そうにデイスってる奴(>>210は別として)最近多いけど、そういうのに限ってこういう基礎が全くわかってない

**デフォルトの名無しさん** · 2019/11/26(火) 19:57:12.90

constexprの利点はtemplateとif constexprの組み合わせがおすすめだと思うの。

◆QZaw55cn4c · 2019/11/26(火) 20:04:28.16

>>210
https://mevius.5ch.net/test/read.cgi/tech/1434079972/51
多桁長演算の乗算・除算もやってみたかったので書いたものです

**デフォルトの名無しさん** · 2019/11/26(火) 20:23:56.31

>>218を読まずに>>220を書いた
コンパイル時に解決するなら0サイクルだ

**デフォルトの名無しさん** · 2019/11/26(火) 20:29:02.34

よく分からない多倍長ライブラリを使うのであれば
当然コンパイル時に解決出来るとは限らない

**デフォルトの名無しさん** · 2019/11/26(火) 20:32:56.90

>>223
多倍長の乗算は筆算の要領で出来るの算数程度の数学で足りるが、
多倍長の除算は、CPUが持っている除算命令を使って行おうとすると
数学的な考える力が必要になる。アルゴリズムは既に有ることはあるはずだが、
丁寧に解説されているわけではないので自分の力で証明できるくらいの
人で無いと難しいと思う。

**デフォルトの名無しさん** · 2019/11/26(火) 20:35:31.27

>>226
素人が適当な事を言わない方が良いかと

**デフォルトの名無しさん** · 2019/11/26(火) 20:39:17.37

多倍長の乗算は、
非常に桁数が少ないときのみ筆算方式
もうちょっと大きいとカラツバ
もっと大きいとフーリエ変換

除算はニュートン法が一般的かと

もちろん、
特殊な形だと特殊な方法があったりする

◆QZaw55cn4c · 2019/11/26(火) 20:47:20.16

>>226
それは乗算と除算が逆なのでは？
除算は筆算流しか手はありません、乗算はいろいろなやりかた（カラツバ・FFT)があるようです

◆QZaw55cn4c · 2019/11/26(火) 20:48:04.78

>>228
＞除算はニュートン法が一般的かと
ニュートン法で剰余を求めることはできますか？

**デフォルトの名無しさん** · 2019/11/26(火) 20:49:49.76

>>230
そりゃ当然出来ますよ

桁数が大きいときは、
除算は乗算の3倍程度の時間で出来ます

**デフォルトの名無しさん** · 2019/11/26(火) 20:51:56.72

除算を筆算方式なんかでやってたら日がくれる

**デフォルトの名無しさん** · 2019/11/26(火) 20:54:28.73

分子の桁数が大きくて分母の桁数が非常に小さい場合のみ筆算方式が有効

この場合も、
非常に遅い割り算命令なんかは使いませんが

**デフォルトの名無しさん** · 2019/11/26(火) 20:56:28.50

>>229
>除算は筆算流しか手はありません
そうではありません。除算をCPUにある除算命令を使った筆算で行うには、x/y の
xのBIT数を増やすのは容易ですが、yの方のBIT数を増やすのは非常に難しいのです。
不可能では有りませんが、非常に数学的な注意が必要となります。
私は数学マニアみたいなものなので、自分なりのアルゴリズムを作ったことが
ありますが、個人的には、それをするためにはテーラー展開の剰余項や解析学的な
知識が必要だと思っています。
考えもしませんでしたが、他にも除算は、ニュートン方を使う流儀もあるそうです。

**デフォルトの名無しさん** · 2019/11/26(火) 20:58:37.06

>>233
いえ、そうでもありません。テーラー展開の剰余項を注意深く扱うと、
CPUがもつdiv命令を使った筆算の場合でも、x/y の y の方のBIT数を
増やすアルゴリズムがありえます。何度も書いてますが、それは数学的に
とても慎重さを必要とします。

**デフォルトの名無しさん** · 2019/11/26(火) 21:00:22.71

>>235
ただし、ニュートン法を使う方法については考えたことがなかったので、
どっちが効率が良いかは分かりません。

**デフォルトの名無しさん** · 2019/11/26(火) 21:03:02.62

>>235
普通のPCのDIV命令は30サイクル近くもかかる
乗算は1～4サイクル
スーパーコンピューターでも除算は非常に遅い

>>233の条件では
除算命令などは使わない方が速い
除算は乗算に置き換えるのが普通

**デフォルトの名無しさん** · 2019/11/26(火) 21:04:44.09

分母、分子それぞれの桁数によって
最適な方法は変わる

だからそういった条件をセットで語らないと意味がない

**デフォルトの名無しさん** · 2019/11/26(火) 21:06:41.35

巨大な桁数同士だとニュートン法が速い
乗算の3倍ほどの時間で出来る

割り算を組み合わせたらそんな時間では計算出来ない

◆QZaw55cn4c · 2019/11/26(火) 21:15:26.74

>>231
ニュートン法（にゅーとんらぷそん）って、曲線で与えられる関数の根の一つを求める方法でしょ？
いわゆる実数の根を求める方法であって、整数の剰余を求めることはニュートン法では無理なのでは？

何がどうなって「当然」なんですか？

**デフォルトの名無しさん** · 2019/11/26(火) 21:19:25.20

除算が出来るんだから剰余も当然求められる

◆QZaw55cn4c · 2019/11/26(火) 21:22:34.40

>>241
で、その剰余はどうやって求めるのですか？
まさか、求めた商に除数をかけて被除数から引くのですか？それって遅くないですか？

**デフォルトの名無しさん** · 2019/11/26(火) 21:23:39.77

遅くないです

◆QZaw55cn4c · 2019/11/26(火) 21:25:15.97

>>243
本当ですか？わざわざ、あらためて掛け算をするんですよ？私には馬鹿みたいな方法にみえますが？

**デフォルトの名無しさん** · 2019/11/26(火) 21:26:45.06

馬鹿みたいな方法にみえるのはあなたが馬鹿だからです

**デフォルトの名無しさん** · 2019/11/26(火) 21:29:07.44

>>242
ニュートン法なので、
z = b / a の z を求めたい場合、直線 y = a * x - b と x 軸(y=0) との交点の
x を求めることによって行う。その際、x0, x1, ・・・, xn のように x を
漸化的に交点に近づけていく。数学的直感だと、その途中で剰余も求められ
るように出来そうな気がする。

**デフォルトの名無しさん** · 2019/11/26(火) 21:43:45.68

>>246
色々なやり方はあると思うけど、2^m <= a < 2^(m+1) の場合、
x_{k+1} = x_k - (y_k << m);
y_{k+1} = a * x_{k+1} - b;
の漸化式でいけるかも知れない。
間違っていたらゴメンなさい。

**デフォルトの名無しさん** · 2019/11/26(火) 21:44:43.61

>>246
その方法で乗算の3倍の時間で除算が出来ますか？
無理ですよね？

**デフォルトの名無しさん** · 2019/11/26(火) 21:49:53.94

>>248
漸化式が三回くらい行ったら正しい答えに到達するのであれば、
乗算の三倍程度の時間で済むと思う。
何回で到達するかは、まだ考えて無いのでわからない。

**デフォルトの名無しさん** · 2019/11/26(火) 21:53:39.27

>>247
ここで、0<= y_k < x_k が満たされれば、x_k が商、y_k が余りだと思う。
初期条件は、
x_0 = 1;
y_0 = a * x_0 - b;
とすればよいはず。
途中、y_k が負の値になることが有るが、問題ない。

**デフォルトの名無しさん** · 2019/11/26(火) 21:55:42.20

前提は分母も分子も巨大な桁数で良いんだよね？

**デフォルトの名無しさん** · 2019/11/26(火) 21:56:38.32

分母の桁数があまり大きくないならテーラー展開も有効だよ

**デフォルトの名無しさん** · 2019/11/26(火) 21:57:23.51

>>251
一般的な場合を取り扱うのであれば、その条件が、もっともらしいと思います。

**デフォルトの名無しさん** · 2019/11/26(火) 21:57:37.73

いずれにしろ、
除算命令を多用することは無い

**デフォルトの名無しさん** · 2019/11/26(火) 21:58:41.68

ニュートン法を使うのは初めて聞きました。
とても勉強になります。

**デフォルトの名無しさん** · 2019/11/26(火) 21:59:47.69

>>253
それで漸化式3回なんてことはあり得ないかと

**デフォルトの名無しさん** · 2019/11/26(火) 22:01:24.02

○<< m とせずに ○<< (m+1) としておけば、y_k は負の数にならないかも
知れない。ただ、数学的直感的に、収束速度は、前者の方が速い気がする。

**デフォルトの名無しさん** · 2019/11/26(火) 22:03:05.27

>>240
数年前にも｢にゅーとんらぷそん｣とか書いてた糞コテがいたんですが
もしかして本人？
文のレベルも頭の悪さもそれっぽい

**デフォルトの名無しさん** · 2019/11/26(火) 22:07:18.12

八木アンテナを八木宇田アンテナと書かないのと同程度に
ニュートンラプソン法とは書かないと思っているので
印象に残ってます

◆QZaw55cn4c · 2019/11/26(火) 22:08:38.03

>>258
raphson の ph を摩擦音で読むか、有気破裂音で読むかは、選択可能かと思っていましたが

**デフォルトの名無しさん** · 2019/11/26(火) 22:10:11.81

>>247
まず、シフトの向きが右で、正しくは、○>>○ でした。

**デフォルトの名無しさん** · 2019/11/26(火) 22:16:30.64

>>260
何を指摘されてるのかわかってないwww

**デフォルトの名無しさん** · 2019/11/26(火) 22:19:47.56

>>256
では、BIT SHIFT ではなく、浮動小数点演算にして、以下の様にすれば速くなるかもしれません。

(i) 初期条件
η = 1/a;　　// 多倍長の浮動小数点
x_0 = 1;
y_0 = a * x_0 - b;

(ii) 漸化式
x_{k+1} = x_k - (int_N)(y_k * η);
y_{k+1} = a * x_{k+1} - b;

但し、int_N は、多倍長の浮動小数点を多倍長整数に直す cast。

**デフォルトの名無しさん** · 2019/11/26(火) 22:34:50.59

#include <iostream>
using namespace std;

int main() {
string str = "abc";
cout << &str << endl;
cout << str << endl;
cout << str.c_str() << endl;
return 0;
}

VisualStudio2019のdebugとreleaseとで&strのメモリダンプ内容が異なるのはなぜでしょうか？
debug : 78 f7 b6 00 61 62 63 00
release : 61 62 63 00

**デフォルトの名無しさん** · 2019/11/26(火) 22:34:54.21

1/a が求まれば
あとは乗算2回(と軽い演算)で剰余が求まるでしょ
漸化式にするまでもなく

**デフォルトの名無しさん** · 2019/11/26(火) 22:36:37.97

>>264
デバッグ情報とか破壊検出用データとかじゃ？

**デフォルトの名無しさん** · 2019/11/26(火) 22:37:41.67

>>265
細部までは分かりませんが、直感でなんとなく分かります。
aが32BITの場合なら、一度にほぼ、32BIT分計算が終わる気がします。

**デフォルトの名無しさん** · 2019/11/26(火) 22:42:23.06

>>266
ありがとうございます。
ということはdebug版の呼び出し元(exe)とrelease版の呼び出し先(dll)
間ではstring型を関数の引数にするとバグりますね。

**デフォルトの名無しさん** · 2019/11/26(火) 22:44:29.12

>>267
>>251の前提はどこに？

**デフォルトの名無しさん** · 2019/11/26(火) 22:45:06.01

>>268
そうなりますね。
malloc() や new なども、Debug 版と Release 版ではライブラリに互換性が
有りません。Debug 版では、まさに、破壊検出用の埋め草のような物が入っていたり、
new を行った行番号情報が入っていたりします。

**デフォルトの名無しさん** · 2019/11/26(火) 22:46:50.29

>>270
多謝!!!
しりませんでした。

**デフォルトの名無しさん** · 2019/11/26(火) 22:49:29.81

>>269
私は特に仮定はしていませんが、四倍浮動小数点型などに興味があり、
それを整数演算に置き換えて実装してみようかと思っていたりするので、
割る数も割られる数も同じくらいのBIT数の整数の場合に興味があります。

前に調べたところ、倍精度浮動小数点演算を用いて、四倍精度浮動小数点
の乗算、除算まで実装する方法があるようですね。ただし、その場合、
Intelの内部拡張倍精度(80BIT)方式をONにしていると駄目なんだそうですが。

**デフォルトの名無しさん** · 2019/11/26(火) 22:57:18.80

>>272
4倍弱精度なら
Haswell以降で使えるFMA命令がとても約に立ちます

**デフォルトの名無しさん** · 2019/11/26(火) 22:58:49.33

>>264
こっちで試した限りだと、debugとreleaseでコンソール表示の長さは変わらんかったぞ
x86とx64なら差が出たが

**デフォルトの名無しさん** · 2019/11/26(火) 22:59:27.13

>>265
aがN BIT の場合、例えば、1/a を、64BIT 程度で求めた場合は、
(N / 64) (回) 程度の乗算が必要になりそうです。
1/a を高速に N BIT まで求めるアルゴリズムがありますでしょうか？

**デフォルトの名無しさん** · 2019/11/26(火) 22:59:32.53

それ以前の普通の乗算でも出来るけど

AVXでSIMD化出来るのでたくさん計算するならぜひ

**デフォルトの名無しさん** · 2019/11/26(火) 23:01:27.32

>>273
興味深いです。教えていただければ幸いです。

**デフォルトの名無しさん** · 2019/11/26(火) 23:02:58.56

>>274
メモリダンプという言葉をみおとしていた
スレ汚しすまぬ

**デフォルトの名無しさん** · 2019/11/26(火) 23:05:02.93

>>275
私が何度か除算は乗算の3倍の時間と書いたのは
例えば100万桁同士の除算は100万桁同士の乗算の3倍な時間という意味
乗算命令の回数ではなくて

aが100万桁で1/aを100万桁精度で求めるのは
100万桁同士の乗算の2倍くらいの時間で出来る

**デフォルトの名無しさん** · 2019/11/26(火) 23:10:41.35

例えば、割り算部分をテーラー展開ですか。

**デフォルトの名無しさん** · 2019/11/26(火) 23:17:37.02

>>277
{a_hi, a_lo} と {b_hi, b_lo} の乗算で
a_hi * b_hi を求めてから、
本当の a_hi * b_hi との誤差を求めるところ

c_hi = a_hi * b_hi とやってから
a_hi * b_hi - c_hi
をFMAでやれば誤差が簡単に求まる

**デフォルトの名無しさん** · 2019/11/26(火) 23:19:37.46

fusedな3個の足し算命令とかもあると
加減算も簡単になるんだけど
そんな命令は(他のCPU含めて)見たことがない

**デフォルトの名無しさん** · 2019/11/26(火) 23:24:07.48

a=1+q の時：
y/a=y/(1+q)
=y*{1 - q + q^2 - q^3 + ... }
=y*(1-q*(1-q*(1-q...))}

**デフォルトの名無しさん** · 2019/11/26(火) 23:30:51.74

>>283
この式は、|q|<1の場合にだけ正しいので、
aをa=u*2^n (u = 1.0 + q)の形式に直してから
1/a = 1/(u*2^n)=1/(1+q)*2^(-n)
　　= (1-q*(1-q*(1-q...)))*2^(-n)
とするのですかね。
なるほど、qの精度を考えれば、乗算の回数は2個くらいまで
で済みそうですね。

**デフォルトの名無しさん** · 2019/11/26(火) 23:36:41.80

>>284
すみません、これだと二回では精度が足りなさそうですね。

**デフォルトの名無しさん** · 2019/11/26(火) 23:37:21.85

多倍長の1/aの話なら
テーラー展開は遅すぎて使いませんよ

4倍弱精度の話であれば
除算命令やテーラー展開は使いますが

どれの話をしてるのかわかるようにかいてくれませんか？

>>238 の通りなので

**デフォルトの名無しさん** · 2019/11/26(火) 23:49:53.60

>>286
多倍長の 1/a はどうやって求めたら効率が良いのでしょうか？

**デフォルトの名無しさん** · 2019/11/26(火) 23:53:50.60

>>228

**デフォルトの名無しさん** · 2019/11/27(水) 00:00:48.09

>>288
もしかすると、
y = 1/(a*x) - 1
と
y = 0
の交点をニュートン法で求めるのでしょうか。

**デフォルトの名無しさん** · 2019/11/27(水) 00:02:25.36

>>289
すみません、違いますね。

**デフォルトの名無しさん** · 2019/11/27(水) 00:27:57.72

初歩的な質問ですみません
2つのdouble型実数xとyを引数とし、x/yとy/xの大きい方を返却する関数を作成せよ。xあるいはyのときは0を返却するとする。という問題でコード書いてみたんですがうまくいきませんどこが間違っているのでしょうか

#include<stdio.h>
double func(double,double); /*プロトタイプ宣言*/

int main(void)
{
double a,b;
printf("実数をスペースで区切って入力してください\n");
scanf("%d %d",&a,&b);
printf("%d",func(a,b)); /*呼び出し*/
return 0;
}

double func(double x,double y)
{
if(x/y > y/x) return x/y;
if(y/x > x/y) return y/x;
if(x==0) return 0;
if(y==0) return 0;
}

**デフォルトの名無しさん** · 2019/11/27(水) 00:33:48.17

%dのところがおかしい
それは整数用

**デフォルトの名無しさん** · 2019/11/27(水) 00:42:47.79

ありがとうございます 1時間くらい悩んでたのが馬鹿みたいだ

**デフォルトの名無しさん** · 2019/11/27(水) 00:53:21.44

入力に0を含めてテストするように

**デフォルトの名無しさん** · 2019/11/27(水) 01:11:14.78

ifの順番変えたら完成しました

**デフォルトの名無しさん** · 2019/11/27(水) 02:13:53.15

QZは馬鹿

**デフォルトの名無しさん** · 2019/11/27(水) 02:41:24.38

xとyが等しいケースは書いたんじゃろうか

**デフォルトの名無しさん** · 2019/11/27(水) 11:43:48.59

世にある仕事の数でいうと
java:C#:C++が5:3:1くらいだな。

**デフォルトの名無しさん** · 2019/11/27(水) 12:16:41.56

このスレ過疎かと思ったら話題でた途端に加速するな

**デフォルトの名無しさん** · 2019/11/27(水) 13:47:03.06

const は要らない子

**デフォルトの名無しさん** · 2019/11/27(水) 14:58:41.90

本当はね・・・constの逆が欲しいのさ
デフォが書き込み禁止で許可を明示だったらと

キャプチャのmutableみたいな

**デフォルトの名無しさん** · 2019/11/27(水) 15:05:41.36

めんどくさいだけ

**デフォルトの名無しさん** · 2019/11/27(水) 15:08:54.83

Pointという点を表すクラスがあって、２点間の距離を取得する関数を追加したいのですが、
double Point::GetDistance(const Point &p) const
にすべきか、ただのCの関数で
double GetDistance(const Point &p1, const Point &p2)
にしたほうがいいのか迷っています。
設計的にいいのはどっちなんでしょうか？

**デフォルトの名無しさん** · 2019/11/27(水) 15:13:19.55

>>303
下
Pointに必要以上の機能を作らない

**デフォルトの名無しさん** · 2019/11/27(水) 15:32:27.13

下に1票。同じ理由

**デフォルトの名無しさん** · 2019/11/27(水) 15:33:34.15

下だな
なんでもかんでもインスタンスに生やすのは厨臭くてダサいし、対称な操作は対象に見えるべき

**デフォルトの名無しさん** · 2019/11/27(水) 15:34:48.68

>>304
ありがとうございます。
ですよね。前者の考えでいくと、いくらでもメンバ関数が増えそうな気がしていました。

**デフォルトの名無しさん** · 2019/11/27(水) 15:43:43.07

下の方が、スカラー値等の既存型や配列向けの特殊化をし易いメリットもあるかもねー

**デフォルトの名無しさん** · 2019/11/27(水) 15:55:14.01

ベクトルの引き算を定義してやるのはありでは

**デフォルトの名無しさん** · 2019/11/27(水) 16:11:06.28

下を造っておいて
operator - で下のを利用 >>309 と同じ
どちらも inline

**デフォルトの名無しさん** · 2019/11/27(水) 16:12:16.87

ああ同じではないわ
ベクトルの引き算はスカラーじゃなくてベクトル
ベクトルの絶対値を定義する

**デフォルトの名無しさん** · 2019/11/27(水) 16:29:07.34

abs(a-b)

**デフォルトの名無しさん** · 2019/11/27(水) 18:11:30.16

ベクトルの加減算や符号は紛れが無いのでオペレータで実装

乗算は内積、外積と要素ごとの積の3種類あるので
関数にする

3次元ベクトルも作る可能性があるなら
2次元ベクトルだとわかる名前にしておく
可能性が無いならそのままで

絶対値やノルム、象限などをグローバルにするかメンバ関数にするかは一長一短
設計ポリシー次第

◆QZaw55cn4c · 2019/11/27(水) 19:16:22.98

>>303
私も下
＞double GetDistance(const Point &p1, const Point &p2)
を friend 関数にします、大事にするのは対照であること、です