geometry > 連番から分岐経路番号を取得する実装 (上部:4分岐, 最下部のみ:3分岐)> v0.5: 直値でのd値取得関数のチェック

動作環境

GeForce GTX 1070 (8GB)
ASRock Z170M Pro4S [Intel Z170chipset]
Ubuntu 16.04 LTS desktop amd64
TensorFlow v1.2.1
cuDNN v5.1 for Linux
CUDA v8.0
Python 3.5.2
IPython 6.0.0 -- An enhanced Interactive Python.
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609
GNU bash, version 4.3.48(1)-release (x86_64-pc-linux-gnu)

v0.1: geometry > 連番から分岐経路番号を取得する実装 (上部:4分岐, 最下部のみ:3分岐)> v0.1, v0.2

やろうとしていること

geometry > sub-triangles > Triangular van der Corput列 > v0.1 > for文のネスト
の方法を使う場合、連番から分岐経路番号(d値)を取得する必要がある。

T(d1, d2) = (T(d1))(d2)

T(d1, d2, d3) = ((T(d1))(d2))(d3)

のような感じ。

ただし、d1,..d{n_1}は{0..3}の値を取り、最後のdn(例: d3)だけ{1..3}の値を持つとする。
(d値が0となる点は若い連番ですでに取得しているという理由から)

v0.5

@shiracamus さんのコメントにいただいたように、「直値と比較をする方が確か」だと思いました。

直値を比較するため、d値から元の値を取得するcalc_decimal()を追加しました。

元の値の取得は以下を考慮しました。

• 上部は4分岐 (0..3)
  • 4進数計算の利用
• 最下部は3分岐 (1..3)
  • 上部の４進数計算 * 3

code

idxToDary_171014.py

import numpy as np
import math
import sys

# on Python 3.5.2

# v0.5 Oct. 21, 2017
#  - refactor > function names
#  - test dvalues by converting back into the original value
#    + add calc_upper_base4()
#    + add calc_start_index()
#    + add calc_decimal()
# v0.4 Oct. 17, 2017
#  - replace test_dvalues() with a different algorithm
#     + add convert_to_dvalues()
# v0.3 Oct. 14, 2017
#  - add test_dvalues()
#  - add calc_dvalues()
# v0.2 Oct. 14, 2017
#  - refactor
# v0.1 Oct. 14, 2017
#  - add show_dvalues()
#  - add get_depth()


def get_depth(idx):
    if idx == 0:
        return 1
    depth = int(math.log(idx, 4))+1
    return depth


def calc_dvalues(idx):
    depth = get_depth(idx)
    # print(idx, depth, end=': ')

    # MSB
    if depth == 1:
        d1 = idx % 4
        # print(d1)
        return [d1]
    remnant = (idx - 4**(depth-1))
    d1 = remnant // 4**(depth-2) // (4-1)
    # print(d1, end=' ')

    res = [d1]
    # inbetween
    for mi in range(depth-1, 1, -1):
        dm = remnant // (4**(mi-2)) // (4-1) % 4
        # print(dm, end=' ')
        res += [dm]

    # LSB
    last = remnant % (4-1) + 1
    # print("", last)
    res += [last]
    return res


def show_dvalues(idx):
    res = calc_dvalues(idx)
    print(idx, res)


def convert_to_dvalues(decimal, base):
    if decimal < base:
        return [decimal]
    res = [(decimal - 1) % (base-1) + 1]
    while decimal >= base:
        res += [(((decimal - base) * base // (base-1)) // base) % base]
        decimal //= base
    res.reverse()
    return res


def calc_start_index(depth):
    return 4**(depth-1)


def calc_upper_baseN(inlist, base):
    copied = inlist.copy()
    del copied[-1]  # last d value is excluded because it is not base 4
    wrk = 0
    for idx in range(len(copied)):
        if idx > 0:
            wrk *= base
        wrk += copied[idx]
    return wrk


def calc_decimal(dvalues, base):
    if len(dvalues) == 1:
        return dvalues[0]
    upr = calc_upper_baseN(dvalues, base)  # upper d values are [0..base-1]
    upr *= (base-1)  # last d value is [1..base-1]

    lastidx = len(dvalues) - 1

    res = calc_start_index(len(dvalues))
    res += upr
    res += dvalues[lastidx] - 1  # -1: because [1..base-1]
    return res


def test_dvalues():
    base = DVAL_BASE
    depth = MAX_DEPTH
    for idx in range(base ** depth):
        res1 = convert_to_dvalues(idx, base)
        res2 = calc_dvalues(idx)

        dcm = calc_decimal(res1, base)

        if idx == dcm:
            print('.', end='')
        else:
            print('!', end='')
    print()


MAX_DEPTH = 5
DVAL_BASE = 4


test_dvalues()
sys.exit()  # ------------------

# test
for idx in range(18):
    show_dvalues(idx)

show_dvalues(63)
show_dvalues(64)

show_dvalues(255)
show_dvalues(256)

show_dvalues(1023)
show_dvalues(1024)

結果

$ python3 idxToDary_171014.py ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

あっているようです。