Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.
動作環境
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)
    • 上部の4進数計算 * 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
................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................

あっているようです。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした