コグノスケ


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

link もっと前
   2022年 1月 5日 ---> 2021年 12月 27日
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年 1月 6日 03:58)

コメント一覧

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



2021年 12月 28日

DUNGEON ENCOUNTERS - まとめリンク

目次: DUNGEON ENCOUNTERS - まとめリンク

日記が増えすぎて、一覧が欲しくなってきたので作りました。とは言ったものの、もう増える気がしない。

編集者: すずき(更新: 2022年 1月 12日 17:33)

コメント一覧

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



2021年 12月 27日

DUNGEON ENCOUNTERS 完全踏破

目次: 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本とスピード重視装備で挑んでみましたけど、防御すら削りきれないうちに瞬殺されて心が折れました……。勝てる気がしません。もういいわ。

編集者: すずき(更新: 2022年 1月 12日 17:34)

コメント一覧

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



link もっと前
   2022年 1月 5日 ---> 2021年 12月 27日
link もっと後

管理用メニュー

link 記事を新規作成

合計:  counter total
本日:  counter today

link About www.katsuster.net
RDF ファイル RSS 1.0
QR コード QR コード

最終更新: 1/24 03:02

カレンダー

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

最近のコメント 5件

  • link 22年01月16日
    すずき 「なるほど、低圧はお米を炊くときに便利なん...」
    (更新:01/18 14:29)
  • link 22年01月16日
    hdk 「圧力鍋で米を炊く時は、100kPaで炊く...」
    (更新:01/17 23:59)
  • link 21年03月04日
    すずき 「なるほど。setupCommandsでg...」
    (更新:01/14 09:16)
  • link 21年03月04日
    名無し 「setupCommandsに\n{"te...」
    (更新:01/13 17:10)
  • link 20年06月19日
    すずき 「お役に立てて何よりです。これ、わかりにく...」
    (更新:09/27 17:05)

最近の記事 3件

link もっとみる
  • link 18年09月21日
    すずき 「[PSP のバッテリー] PSP を久しぶりに見たところ、バッテリ...」
    (更新:01/24 03:02)
  • link 21年03月06日
    すずき 「[気に入るマウスはどれ?] 手に合うワイヤレスマウスを探し続け、高...」
    (更新:01/21 18:42)
  • link 22年01月17日
    すずき 「[SPI ディスプレイを動かしてみる] 昨年、秋月で買って放置して...」
    (更新:01/19 23:25)

こんてんつ

open/close wiki
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 過去日記について

その他の情報

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