コグノスケ


link 未来から過去へ表示(*)  link 過去から未来へ表示

link もっと前
2022年1月6日 >>> 2021年12月24日
link もっと後

2022年1月4日

Windows電卓

Windows電卓は浮動小数点数を扱えます。10^9999から10^-9999という非常に大きい数から、小さい数まで扱えます。

単精度浮動小数点数の最小値は10^-38(正規化数)もしくは10^-45程度、倍精度浮動小数点数でも最小値は10^-308(正規化数)もしくは10^-324(非正規化数)程度ですから、IEEE 754準拠の浮動小数点数型ではなさそうです。


Windows電卓で1 - 1.e-204 - 1を計算した結果

そのためか少し変わった桁落ちの挙動を示します。同じ程度の大きさの数同士の演算(例: 1.e-9999 + 1.e-9999 = 2.e-9999)であれば桁落ちしませんが、大きい数と小さい数を演算(例: 1 - 1.e-204 - 1 = -9.807971461541689e-149)すると激しく桁落ちします。

Windows電卓はオープンソース

実はWindows 10の電卓のソースコードはGitHubに公開されていてGitHubのプロジェクトへのリンク)、誰でも見ることができます。MITライセンスで、2019年に公開されたそうです。Windowsの標準アプリがオープンソースになっているなんて、調べるまで知りませんでした。

利用方法は簡単でGit cloneしたあと、Visual Studioでsrcディレクトリの下にあるCalculator.slnを開くだけです。私のノートPCが非力なせいか、ビルドは非常に遅いですね……。


デバッグの設定

デバッグする際は、設定を「マネージド+ネイティブ」にしておかないと、ネイティブコードを実行している部分のデバッグが全くできず、ブレークポイントなどが無視されるので注意が必要です。

桁落ちしている箇所

コードのありかとデバッグ方法がわかったところで、Windows電卓のコードを調べます。桁落ちはどこで発生しているでしょうか?

先ほど示した1 - 1.e-204 - 1という演算の場合、CalcManagerプロジェクトのRatPack/rat.cppのaddrat() 関数にてtrimit() を呼んでいる箇所で桁落ちが発生します。

数値表現と加算の実装

//calculator/src/CalcManager/Ratpack/ratpak.h

typedef uint32_t MANTTYPE;

...

//-----------------------------------------------------------------------------
//
//  NUMBER type is a representation of a generic sized generic radix number
//
//-----------------------------------------------------------------------------

#pragma warning(push)
#pragma warning(disable : 4200) // nonstandard extension used : zero-sized array in struct/union
typedef struct _number
{
    int32_t sign;   // The sign of the mantissa, +1, or -1
    int32_t cdigit; // The number of digits, or what passes for digits in the
                    // radix being used.
    int32_t exp;    // The offset of digits from the radix point
                    // (decimal point in radix 10)
    MANTTYPE mant[];
    // This is actually allocated as a continuation of the
    // NUMBER structure.
} NUMBER, *PNUMBER, **PPNUMBER;
#pragma warning(pop)

//-----------------------------------------------------------------------------
//
//  RAT type is a representation radix  on 2 NUMBER types.
//  pp/pq, where pp and pq are pointers to integral NUMBER types.
//
//-----------------------------------------------------------------------------

typedef struct _rat
{
    PNUMBER pp;
    PNUMBER pq;
} RAT, *PRAT;


//calculator/src/CalcManager/Ratpack/rat.cpp

void addrat(_Inout_ PRAT* pa, _In_ PRAT b, int32_t precision)
{
    PNUMBER bot = nullptr;

    if (equnum((*pa)->pq, b->pq))
    {
        // Very special case, q's match.,
        // make sure signs are involved in the calculation
        // we have to do this since the optimization here is only
        // working with the top half of the rationals.
        (*pa)->pp->sign *= (*pa)->pq->sign;
        (*pa)->pq->sign = 1;
        b->pp->sign *= b->pq->sign;
        b->pq->sign = 1;
        addnum(&((*pa)->pp), b->pp, BASEX);
    }
    else
    {
        // Usual case q's aren't the same.
        //★bを変更できないので見づらい書き方になっているが、通分して加算している
        //★pa = pa->pp / pa->pq = A / B, b = b->pp / b->pq = C / Dとおくと
        DUPNUM(bot, (*pa)->pq);          //★bot = B
        mulnumx(&bot, b->pq);            //★bot = BD
        mulnumx(&((*pa)->pp), b->pq);    //★pa = AD / B
        mulnumx(&((*pa)->pq), b->pp);    //★pa = AD / BC
        addnum(&((*pa)->pp), (*pa)->pq, BASEX);    //★pa = (AD + BC) / BC
        destroynum((*pa)->pq);
        (*pa)->pq = bot;                 //★pa = (AD + BC) / BD
        trimit(pa, precision);    //★★この呼び出しで桁落ち★★

        // Get rid of negative zeros here.
        (*pa)->pp->sign *= (*pa)->pq->sign;
        (*pa)->pq->sign = 1;
    }

#ifdef ADDGCD
    gcdrat(pa);
#endif
}

Windows電卓は内部ではRAT型(struct rat型)で数値を保持しています。RATは分子ppと分母pqの2つのNUMBER型で構成された有理数を表す型です。

有理数の加算は小学校で習った通りで、通分して足します。大きな数+小さな数で通分すると、非常に仮数部(構造体のmant、mantissa: 仮数の意味)が長くなってしまいます。例えば1 + 1.e-9999だと仮数部が9511要素もあるint32_tの配列になります。trimit() は一定以上の仮数を切り落とす役目を果たします。


加算の桁落ちを削除したWindows電卓で1 - 1.e-204 - 1を計算した結果

桁落ちを防止したければtrimit() の呼び出しを削れば良いです。しかし不思議なことに完全にtrimit() を削除するとWindows電卓が起動しなくなります。

桁落ちは必須

桁落ちを防止すると起動しなくなる理由は、Windows電卓はなぜか起動時にCCalcEngineのコンストラクタにて10^100を計算しているからです。

Windows電卓はx^yをx^y = exp(y * ln(x)) で求めているので、logの実装を見ましょう。ソースコードはexp.cppの _lograt() です。見たところ、十分に小さい項までテイラー展開を続けるアルゴリズムのようです。

logの実装

//calculator/src/CalcManager/Ratpack/exp.cpp

void _lograt(PRAT* px, int32_t precision)
{
    CREATETAYLOR();

    createrat(thisterm);

    // sub one from x
    (*px)->pq->sign *= -1;
    addnum(&((*px)->pp), (*px)->pq, BASEX);
    (*px)->pq->sign *= -1;

    DUPRAT(pret, *px);
    DUPRAT(thisterm, *px);

    n2 = i32tonum(1L, BASEX);
    (*px)->pp->sign *= -1;

    do
    {
        NEXTTERM(*px, MULNUM(n2) INC(n2) DIVNUM(n2), precision);
        TRIMTOP(*px, precision);
    } while (!SMALL_ENOUGH_RAT(thisterm, precision));

    DESTROYTAYLOR();
}

桁落ちを一切なくすとループが終わらなくなってしまいます。変数thistermが0にならないとループを抜けないところを見ると、ループ条件のSMALL_ENOUGH_RATがバグっているような気もするんですが……、これ以上の深追いはやめておきます。

他にも √ の計算も非常に遅くなります。パフォーマンスと実用性のバランスからtrimit() は必須といえるでしょう。

編集者:すずき(2022/01/06 03:58)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2022年1月3日

北海道から東京へ

オミクロン株が若干不穏な気配ですが、今年は久しぶりに北海道に帰省しました。でも次の帰省はいつになるやら……。COVID-19の動向次第ですね。

今までは帰省時期に飛行機に乗るとほぼ必ずインフルエンザをもらっていたのですが、今年は風邪一つ引きませんでした。道行く人が全員マスクを着ける、というのは本当に伝染病予防に効くんですね。マスクの効果を疑っていたわけではないですけど、思った以上の効果が出ていて驚いています。

編集者:すずき(2022/02/08 18:43)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする




2021年12月27日

DUNGEON ENCOUNTERS完全踏破

目次: ゲーム

ダンジョンエンカウンターズ、全フロアを踏破しました。基本的には強敵を避けてウロウロ歩けば踏破できますし、アビリティ「ノーエンカウント」取得後は、落とし穴以外に恐れるものは存在せず、ほぼ塗り絵ゲームになります。ただし、地下92階だけはかなり辛いです……。

魔の地下92階

おそらく全員が「最も踏破に苦労する階は?」という質問に対して「地下92階」と答えるでしょう。それくらい面倒くさい作りです。地下92階は全て飛び地になっていて、一部は地下93階から02(上り階段)で行けますが、残りはほとんど目印がありません。マップの背景(宇宙みたいな赤と青のモヤモヤ)から、飛び地の座標に当たりを付け、アビリティ「仮想階段上り」で上る必要があります。

地下92階から「仮想階段下り」で地下93階に戻ると、いきなり落とし穴に落ちることがありますが、地下94階で必ず受け止めてくれるので心配いりません。

しかし落ちた先の地下94階や、地下92階の小島でミスって落とし穴を踏むと「奈落の底に落ちてパーティーが全員行方不明」になることがあります。被害を最小限にするためにも、地下92階は1人パーティーで攻略した方が良いと思います。入り口となる地下93階は常に一本道です。落とし穴回避のためアビリティ「ムーブ」「ナイトムーブ」、エンカウントマスも回避できないため「ノーエンカウント」もほぼ必須でしょう。

全部巡るのは非常に大変でしたが、下記の表で座標を全部メモできているはずです。

島の種類 島の広さ
02階段上り 24116
02階段上り 147220
02階段上り 1513 4
02階段上り 213416
02階段上り 338716
02階段上り 362012
02階段上り 473416
02階段上り 498316
02階段上り 611020
02階段上り 724316
02階段上り 738316
02階段上り 741520
02階段上り 924116
02階段上り 9488 9
Event 3Fの島496025
Event FDの島8714 9
仮想階段上り 55420
仮想階段上り 973 4
仮想階段上り 108312
仮想階段上り 101916
仮想階段上り 145416
仮想階段上り 163012
仮想階段上り 178120
仮想階段上り 182612
仮想階段上り 193912
仮想階段上り 196312
仮想階段上り 244516
仮想階段上り 252020
仮想階段上り 275812
仮想階段上り 277520
仮想階段上り 29 615
仮想階段上り 302916
仮想階段上り 376512
仮想階段上り 3942 9
仮想階段上り 405020
仮想階段上り 419915
仮想階段上り 417920
仮想階段上り 5237 4
仮想階段上り 552020
仮想階段上り 584816
仮想階段上り 619416
仮想階段上り 63 012
仮想階段上り 671920
仮想階段上り 6832 6
仮想階段上り 687716
仮想階段上り 7092 9
仮想階段上り 716516
仮想階段上り 7750 9
仮想階段上り 798016
仮想階段上り 802720
仮想階段上り 8339 6
仮想階段上り 875920
仮想階段上り 896816
仮想階段上り 952520

サイトだと見づらいと思うので、Googleスプレッドシートにも置きました(Googleスプレッドシートへのリンク)。基本的には地下93階の「曲がり角」で仮想階段を使う座標にしたはずです。間違ってたらゴメンなさい&コメントなどで教えてくれると嬉しいです。

攻略の途中で「この地下92階は山勘でやってもクリア不可能じゃね?」と感じてメモを始めたため、踏破済みと未踏破が中途半端に混ざった状態からメモを始めることになりました。おかげで島の座標を全部列挙したかどうかの検証がめちゃくちゃ面倒くさかったです……。最初からメモすれば良かったよー。

真のラスボスは諦めた

「無限」より強いと思われるのが、バトルFDの「モルモット教授」という敵です。出会える確率が非常に低い、防御とHPが9,999,999の最強タフネス、驚異のスピード130、数ターン耐えるのが限界の超強力な攻撃、と嫌な点の塊のような敵です。

幸い?なことにアイテムを何もドロップしませんから、倒す必要がありません。無視してOKです。ただただやり込みプレイを阻むためだけに用意された、嫌がらせのような敵です。

私もアドレスブレイド3本とスピード重視装備で挑んでみましたけど、防御すら削りきれないうちに瞬殺されて心が折れました……。勝てる気がしません。もういいわ。

編集者:すずき(2023/09/24 13:06)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2021年12月26日

DUNGEON ENCOUNTERSクリア

目次: ゲーム

ダンジョンエンカウンターズ、やっと最後まで行きました。謎解きはまじめにやらず、攻略サイトを見てしまいました。難しいというか……正解を見ても「無茶言うなよ」って感じの問題です。攻略サイト作っている人たちはどうやって解いたんでしょうね……?

ラスボス1

地下90階にいるラスボスを倒して1回目のスタッフロールを拝むのはそんなに難しくありません。とはいえ、強いのは確かです。特に2回目の戦闘(パノプティコアA, B, C, D)は、何も考えずに突っ込むとパーティーが蒸発します。ラスボスを無視して、地下99階までの謎解きアイテムとアビリティを全部拾ってから改めて挑むと比較的楽だと思います。アビリティ「テレポ」と「ノーエンカウント」を拾うと回収が捗ります。

  • 武器: アドレスブレイド(単体物理、アドレス依存ダメージ)
  • 武器: ジャベリン(全体物理375,000)
  • 武器: トウルヌソル(単体物理100,000)
  • アビリティ: 防御系全部、HP満タン攻撃力倍、精神統一(飛行に剣や槍が当たる)

謎解きを済ませると、この辺の超強力な武器が全て揃うはずです。地下90階以降の敵はアホみたいに攻撃力が高く、一撃で防御値がなくなることが多いため、防具を1〜2段階強化してもほぼ意味がありません。スピードの落ちる重装備(ヘルム、鎧)より、スピード重視で軽装備(服、帽子)+ブーツにして、相手より早く殴って倒すようにすると良いでしょう。

  • ブーツ: コスト内で速度が一番上がるもの
  • 防具: コスト内で速度の落ちない軽装備、ただし裸は即死するのでNG

パノプティコアは1体だけ残すと「全ての力」という超強烈な攻撃をしてきて、メンバーが一瞬で蒸発するので、

  • HPが低いAを速攻で潰す
  • スピードの速いDをアドレスブレイドで殴りまくって潰す
  • 残ったノロマのBとC 2体をアドレスブレイドで殴り、HPはトウルヌソルで削る
  • 最後にジャベリンで2体同時に倒す

こうすると比較的楽なはずです。

ラスボス2

最下層の地下99階にいるバトルFF「無限」というクッソ強い敵を倒すと2回目のエンディングが拝めます。拾える武器だけでもうまくやれば倒せる気がするんですけど、私はやり方がうまくないのか、火力不足で勝てませんでした。

地下98階辺りの、バトルF7を集中的に選んで、ティアマットLv.99が落とすアドレスブレイドを2本を拾うまで頑張ります。出てくる敵としては、

ティアマットLv.99
メインターゲットです。スピード80で比較的行動が早いうえ、ほぼ確実に全体物理攻撃(咆哮: 割合ダメージなので雑魚、なぎ倒す: 超強烈で物理防御が一撃でなくなる)をしてきて超危険です。幽霊船の番が来ないなら、こいつを集中攻撃で潰しましょう。
幽霊船Lv.99
スピード85、飛行状態、高確率で全体物理攻撃(砲撃: 強烈な物理攻撃、恐怖: 確率で物理防御破壊)をしてくる危険な相手です。ですが幸いなことにHP 1なので、「精神統一」アビリティ、全員を「物理武器+素手」にしておけば、素手パンチをお見舞いして確実に倒せます。ホクガクの刀攻撃も有効です。
ウィールワーターLv.98
単体、全体魔法攻撃を使ってきますが、全体攻撃は半々くらいですかね。スピード65と遅く、攻撃頻度は低いです。先行で魔法攻撃を食らって魔法防御がなくなったとしても、次の攻撃を食らう前に、ジャベリンとアドレスブレイドの順が回ってきて確実になぎ倒せるはずです。

バトルF8の方がティアマットが確実に出ますが、一気に5体出てきて強力な全体物理攻撃を連発され、パーティーが一瞬で全滅する可能性が高く、面倒な相手です。バトルF7を数こなす方が安定すると思います。

アドレスブレイドを揃えたら、地下99階のなるべく南東のマスに「無限」を出現させます。装備はHP満タン攻撃力倍+スピード重視装備+アドレスブレイドで。アドレスブレイド持ちのキャラはとにかく殴り、防御が完全に剥がれたキャラやアドレスブレイドを持っていないキャラは防御回復を連打、これでたぶん倒せるはずです。

編集者:すずき(2023/09/24 13:06)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2021年12月24日

サンタがマッハ2で街にやってくる(2021年)

目次: サンタ

飛行機の位置をリアルタイムに表示するFlightradar24というサービス(サイトへのリンク)があります。飛行機やヘリコプターが発するADS-Bという信号を、世界中の有志が受信して、Flightradar24のサーバーに送ることで実現しているそうです。へえ〜。

仕組みはさておいて、このサービスではクリスマス・イブの日にはサンタが出現する毎年恒例のお約束演出があります。夜にサンタの飛んでいる様をボーっと眺めていました。

マレーシア上空をインド方面に飛んでいましたが、どうも移動速度が速いような気がしてなりません。表示上は40ノット(時速74.8km/h)となっています。しかしマレーシアをあっさりと横断して、インド洋に抜けており、そんなゆっくり飛んでいるように見えません。

サンタの対地速度

サイトの速度表示は無視して、2地点間の距離で速度を測ってみました。


20:27:14時点の位置(緯度9.99903度、経度93.3008度)


20:27:41時点の位置(緯度10.1382度、経度93.2107度)

緯度、経度から距離を出すときは、地球の形状(赤道方向がやや長い、楕円形)を考慮したりで割と面倒らしいんですが、国土地理院のページを使うと一発で計算してくれて超便利です(サイトへのリンク)。


緯度、経度から距離と方位角を計算(国土地理院のサイト)

2地点間の距離は約19.1kmで、時間差は27秒なので、対地速度は約2,546km/hです。地上で言うところのマッハ2くらい(ただし、上空34,000ftsだとマッハ数はもっと高く出る)です。旅客ジェット機は対地速度800km/hくらい(マッハ 〜0.8程度)なので、ジェット機の2〜3倍速です。

戦闘機の巡航速度がマッハ1くらいで、アフターバーナーでマッハ2超えるくらいらしいので、サンタさんめっちゃ速いやん……。戦闘機とやりあう気かよ??

編集者:すずき(2024/01/04 03:18)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



link もっと前
2022年1月6日 >>> 2021年12月24日
link もっと後

管理用メニュー

link 記事を新規作成

<2022>
<<<01>>>
------1
2345678
9101112131415
16171819202122
23242526272829
3031-----

最近のコメント5件

  • link 21年3月13日
    すずきさん (03/05 15:13)
    「あー、このプログラムがまずいんですね。ご...」
  • link 21年3月13日
    emkさん (03/05 12:44)
    「キャストでvolatileを外してアクセ...」
  • link 24年1月24日
    すずきさん (02/19 18:37)
    「簡単にできる方法はPowerShellの...」
  • link 24年1月24日
    KKKさん (02/19 02:30)
    「追伸です。\nネットで調べたらマイクロソ...」
  • link 24年1月24日
    KKKさん (02/19 02:25)
    「私もエラーで困ってます\n手動での回復パ...」

最近の記事20件

  • link 24年3月25日
    すずき (03/26 03:20)
    「[Might and Magic Book One TASのその後] 目次: Might and Magicファミコン版以前(...」
  • link 21年10月4日
    すずき (03/26 03:14)
    「[Might and Magicファミコン版 - まとめリンク] 目次: Might and Magicファミコン版TASに挑...」
  • link 24年3月19日
    すずき (03/20 02:52)
    「[モジュラージャックの規格] 古くは電話線で、今だとEthernetで良く見かけるモジュラージャックというコネクタとレセプタク...」
  • link 23年4月10日
    すずき (03/19 11:48)
    「[Linux - まとめリンク] 目次: Linuxカーネル、ドライバ関連。Linuxのstruct pageって何?Linu...」
  • link 24年3月18日
    すずき (03/19 11:47)
    「[画面のブランクを無効にする] 目次: LinuxROCK 3 model CのDebian bullseyeイメージは10分...」
  • link 24年3月3日
    すずき (03/19 11:07)
    「[解像度の設定を保存する] 目次: LinuxRaspberry Pi 3 Model B (以降RasPi 3B)のHDMI...」
  • link 24年3月14日
    すずき (03/16 23:03)
    「[JavaとM5Stamp C3とBluetooth LE - Bluetoothデバイスとの通信] 目次: ArduinoM...」
  • link 24年3月8日
    すずき (03/16 23:03)
    「[JavaとM5Stamp C3とBluetooth LE - BluetoothデバイスとServiceの列挙] 目次: A...」
  • link 23年6月2日
    すずき (03/16 21:11)
    「[Arduino - まとめリンク] 目次: Arduino一覧が欲しくなったので作りました。 M5Stackとesp32とA...」
  • link 23年5月15日
    すずき (03/16 00:57)
    「[車 - まとめリンク] 目次: 車三菱FTOの話。群馬県へのドライブ将来車を買い替えるとしたら?FTOのオイル交換とオイル漏...」
  • link 24年3月9日
    すずき (03/16 00:56)
    「[車のバッテリー完全に死亡で交換かと思いきや] 目次: 車またまた車のバッテリーが干上がって死にました。写真は撮っていませんが...」
  • link 24年3月10日
    すずき (03/15 03:34)
    「[誕生日] 早いもので41歳になりました。昨年の日記(2023年3月10日の日記参照)を見ると、コロナの流行を心配していました...」
  • link 24年3月6日
    すずき (03/12 01:18)
    「[Raspberry Pi 3 model Bの代わりにROCK 3 model C] 目次: Arduino最近、M5Sta...」
  • link 24年3月4日
    すずき (03/06 00:09)
    「[volatileをnon-volatileで参照してはいけない] 目次: GCC過去の日記(2021年3月13日の日記参照)...」
  • link 20年6月2日
    すずき (03/06 00:06)
    「[GCC - まとめリンク] 目次: GCCGCCについて。GCCを調べる - その1 - ビルドGCCを調べる - その2 ...」
  • link 15年5月9日
    すずき (03/05 03:00)
    「[自作ARMエミュレータ - 今さら気づいたブートローダのバグ] 目次: Linuxずっと気づいていなかった自作ARMエミュレ...」
  • link 23年6月1日
    すずき (03/05 02:59)
    「[自宅サーバー - まとめリンク] 目次: 自宅サーバーこの日記システム、Wikiの話。カウンターをPerlからPHPに移植日...」
  • link 15年5月3日
    すずき (03/05 02:59)
    「[GRUB2が起動しなくなってしまった] 目次: 自宅サーバーサーバにインストールしていたDebian 32bit版 のJes...」
  • link 15年5月2日
    すずき (03/05 02:58)
    「[systemdを使うのをあきらめた] 目次: 自宅サーバー独自ビルドのカーネルだと/sys/fs/cgroupが無いと言われ...」
  • link 15年4月30日
    すずき (03/05 02:56)
    「[Debian 8.0 Jessie] 目次: 自宅サーバーDebianのアップデートが来ていたので、試しに職場のPCをアップ...」
link もっとみる

こんてんつ

open/close wiki
open/close Linux JM
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 2024年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDFファイル RSS 1.0

最終更新: 03/26 03:20