is fibo

주어진 숫자가 fibonacci number인지를 알아보는 것이 목표인데, 처음부터 조금 쉽게 해보려고 삽질을 하다가 괜한 시간만 보냈다.

위키에도 있지만 \(5x^2 + 4\)나 \(5x^2 -4\)중 하나만 perfect square여도 \(x\)가 fibonacci number이다. 문제는 이런식으로 하려면 data type때문에 숫자가 조금만 커져도 풀 수가 없어진다는 점. 주어진 열자리 수가 fibonacci number인줄 알기 위해서는 \(5\times x \times x\)를 계산해야 하는데 금방 스무자리가 넘어간다. 아주 큰 수의 square root를 어떻게 계산해야 하는지는 좀 더 찬찬히 생각해 봐야 할 것 같다.

이 문제가 의외였던 점은, brutal force로 해도 열자리 정도에는 금방 도달한다는 점. 1,1,2,3,...으로 진행되는 squence에서 99번째면 서른자리¹⁾에 도달하고 996번째면 300자리²⁾에 도달한다. 

위키페이지를 보다가, ‘The Fibonacci Quarterly’라는 저널이 있다는 것도 알았다. 세상엔 참 별의별 저널이 다 있다.

---

1) 118842243771396506390315925504
2) 125567414904640701673643560436718962175164626371742219622314498637150513803703451854671685017464358374327500732525759393576618588167068051984194268453498923483608216111221456860403218028074661818882275572106013378713850874227329307333971218118090581030131208722889166027270662089679192033248503922688

binary gap

binary gap문제.

이렇게 생겼다. (링크)
아래는  python으로 짜본거.

from math import log
def tz(n): #trailing zeros
    return int(log(n - (n&(n-1)), 2)) #= int(log(n& -n, 2))
 
def binarygap(n):
    sol = 0
    while True:
        n = n >> (tz(n) + 1)
        if n == 0 : break
        sol = max(sol, tz(n))
    return sol

위에 trailing zeros 얻는 과정(n- (n&(n-1)))이 약간 tricky한데, 천천히 생각해보면 알 수 있다.
아래는 n&-n의 계산된 몇가지 예시. 보면 대충 알 수 있다.
>>> for i in range(1, 40):
...     print bin(i), bin(i & -i)
... 
0b1 0b1
0b10 0b10
0b11 0b1
0b100 0b100
0b101 0b1
0b110 0b10
0b111 0b1
0b1000 0b1000
0b1001 0b1
0b1010 0b10
0b1011 0b1
0b1100 0b100
0b1101 0b1
0b1110 0b10
0b1111 0b1
0b10000 0b10000
0b10001 0b1
0b10010 0b10
0b10011 0b1
0b10100 0b100
0b10101 0b1
0b10110 0b10
0b10111 0b1
0b11000 0b1000
0b11001 0b1
0b11010 0b10
0b11011 0b1
0b11100 0b100
0b11101 0b1
0b11110 0b10
0b11111 0b1
0b100000 0b100000
0b100001 0b1
0b100010 0b10
0b100011 0b1
0b100100 0b100
0b100101 0b1
0b100110 0b10
0b100111 0b1

비트를 하나하나 순차적으로 검사해도 O(log n)이라 연산을 저렇게 tricky하게 해도 complexity의 이득은 없다. worst case에서는 둘 다 O(log n). best case에서 큰 차이가 난다. O(log log n)

비슷한 원리로, binary로 나타냈을 때 1이 몇개 나오는지 맞추는 문제도 있다.
python코드는 다음과 같다.

def howmany1s(n) :
     count = 0
     while(n >0):
             n = n&(n-1)
             count += 1
     return count

\( \int_5^6 e^{x^{0.4889982575}} \)

\(\approx 10\)

심심해서.

유효숫자의 영향을 많이 받는 것 같다. CASIO계산기로 했을 때는 0.488998257396018이었고, 끝에 8을 7999999~로 바꿔도 답이 동일했다.
MATLAB을 가지고 해봤는데 이건 이상하게 결과가 변화가 없는 선이 어디까지인지 모르겠다. numerical integral인데 설마 precision이 \(\infty\)는 아닐 것이고...

integral(@(x) exp(x.^0.488998257408731679118929491778544615954161), 5, 6)

여기까지 해봤다. 저기서 소수 끝자리를 계속 늘려가면  9.99999999999999와 10 사이를 계속 오락가락 한다. 실행 전 format long e 해야 한다. 기본값은 short다.

밑줄 친 부분이 답이 서로 다른 부분인데, 셋 다 옳을 수는 없으므로 셋중에 적어도 둘은 값이 부정확한 것이다. Wolfram alpha로 해보면,

0.4889982574087317906738955163926...으로 10에 근접한다.
밑줄 친 부분부터 MATLAB과 다르나 보통 숫자는 mathematica가 더 정확하다고들 한다.

어찌되었건 계산기는 (계산결과 뿐 아니라)입력부터 소수 열째자리정도 부터는 신뢰하기 힘들다는 교훈.

같다/다르다

‘얼마만큼 같냐’와 ‘얼마만큼 다르냐’는 동전의 양면같이 서로 본질을 공유하는 듯 하면서도 막상 숫자로 나타내려면 아예 둘이 서로 다르다. ‘\(0\)만큼 다르다’는 직관적이지만, ‘\(0\)만큼 같다’거나 ‘\(10000\)만큼 같다’는 조금 이상하지 않은가. ‘\(\infty\)만큼 같다’도 이상하기는 마찬가지다.

영어

Since that time, Scholze, now 28, has risen to eminence in the broader mathematics community. Prize citations have called him “already one of the most influential mathematicians in the world” and “a rare talent which only emerges every few decades.” He is spoken of as a heavy favorite for the Fields Medal, one of the highest honors in mathematics.

출처: https://www.quantamagazine.org/20160628-peter-scholze-arithmetic-geometry-profile/

Prize citations는 뜻도 잘 이해가 안간다.

Spiral Matrix

size nr×nc의 spiral matrix에서 (r, c)의 좌표에 있는 숫자N은 다음과 같다.

n1 = min(r, c, nr-1-r, nc-1-c)
n2 = (r == n1 || (nc-1-c) == n1)? c + r - 2*n1 : 2*nc + 2*nr - 6*n1 - r - c
N = n1*2*(nr+nc-2) - 4*n1*(n1-1) + n2

Clustering

http://link.springer.com/article/10.1007/s40745-015-0040-1

survey하나 링크.

1. Classical

    A. Partition

        k-means, k-medoids, PAM, CLARA, CLARANS

        not suitable for non-convex data

    B. HIERARCHY

        BIRCH(CF tree), CURE(random sampling, large scale clustering), ROCK(improvement of CURE. about enumeration type), Chameleon

    C. Fuzzy

        FCM: ‘object function’

        FCS: distance function by multi-dimensional hypersphere

        MM: Mountain function → find the center of cluster

        relatively high accuracy.

        easily drawn into local optimal.

    D. Distribution

        DBCLASD

            same distribution → same cluster

        GMM

            several gaussian distributions, high scalablity.

    E. Density

        high density → same cluster

        DBSCAN *

        OPTICS : improvement of DBSCAN

            1) radius of neighborhood

            2) min number of pts in a neighborhood

        Mean-Shift *

        pros

            high efficiency

            arbitrary shape

        cons

            density에 따라 결과가 안좋을 수 있음

            big size memory

            sensitive to parameters

        DENCLUE : large scale data clustering

    F. GRAPH Theory

        1) CLICK : min weight of division of the graph

        2) MST(minimum spanning tree)-based clustering

        pros

            high efficiency

            high accuracy

        cons

            time complexity grows as graph's complexity grows.

        SM, NJW algorithm need to be considered

    G. Grid

        original data space → grid structure

        1) STING

            a. divided into many rectangular by constructing hierarchical structure

            b. parallable

        2) CLIQUE

            grid based + density based

        pros

            low time complexity

            high scalability

        cons

            accuracy-efficiency trade-off

        wave cluster와 관련되어 있음

    H. Fractal Theory

        FC : change of any inner data of cluster does not have any influence on the instrinsic quality of the fractal dim. O(n)

        sensitive to parameters

    I. Model

        1) Statistical learning

            COBWEB : probability dist of each attr. is indenpendent

        2) Neuralnet

            a. SOM : build a mapping of dimension reduction.(assumption: there exists topology in the input)

            b. ART : incremental algorithm. generates a new neuron.

        time complexity : COBWEB < ART < SOM

2. MODERN

    A. Kernel

        kernel k-means

        kernel SOM

        kernel FCM

        SVC : sphere in feature space → original data space (isoline: border of clusters)

        MMC : hyperplane with maximum margin

        MKC : improvement of MMC

        pros

            can sepearate overlapping clusters.

            not need preliminary knowledge about topology of data

        cons

            not good for large scale data(time complexity high)

            sensitive to kernels and there parameters

    B. Ensemble

        initial clustering → (consensus function) → final result.

        어지간하면 그냥 제일 좋을듯.

    C. Swarm

        simulate the changing process of the biological population

        time complexity high

        easy to understand

        low scalability

    D. Quantum Theory

        QC : getting potential energy by Schrodinger.

        DQC: improvement of QC. time based Schrodinger Eq.

    E. Spectral Graph

        graph partitioning.

        1) recursive spectral : SM (Normalized cut이용한 image segmentation과 비슷)

        2) multiway spectral : NJW (feature space by k-largest eigenvalues of the Laplacian Matrix)

        time complexity high

        Not sensitive to outliers

        number of clusters needed to be preset

    F. Affinity Propagation (AP ★)

        simple, clear idea

        N is not deeded (N: number of clusters)

    G. Density and Distance (DD ★)

        arbitrary shape

        insensitive to outliers(but sensitive to parameters)

        time complexity high

    H. Spatial Data

        DBSCAN, STING, Wavecluster(parallel processing possible), CLARANS(sample based CLARA + clustering by PAM)

    I. Data Stream

        STREAM

        CluStream ┐

        HPStream  ┼ incremental

        DenStream ┘

    J. Large Scale Data

        4V ┬ large in volume

           ├ rich in variety

           ├ high in velocity

           └ doubt in veracity(정직성, 진실성, 정확도)

        1) sample

        2) data merge

        3) dimension reduction

        4) parallel