Script Programming(스크립트 프로그래밍)

피보나치 수열이 0 이상의 정수 n에 대하여

         선형점화공식(linear recurency):  f(n) = f(n - 1) + f(n - 2) 과

         과 초기조건(initial condition):  f(0) = 0,  f(1) = 1

로 정의된 수열인데 이를 음의 정수 n에 대하여도 위의 점화공식을

             f(n) = f(n + 2) - f(n + 1)     (∀ n = -1, -2, -3, -4, -5, ...)

로 고쳐 축차 적용하여 얻어지는 수열

   f(-1), f(-2), f(-3), f(-4), f(-5), ....

을 네가보나치 수열(negabonacci sequence)이라고 한다.

   즉,

             f(-1) = f(1) - f(0) = 1 - 0 = 1

             f(-2) = f(0) - f(-1) = 0 - 1 = -1

             f(-3) = f(-1) - f(-2) = 1 - (-1) = 2

             f(-4) = f(-2) - f(-3) = -1 - 2 = -3

             f(-5) = f(-3) - f(-4) = 2 - (-3) = 5

             f(-6) = f(-4) - f(-5) = -3 - 5 = -8

             ..............................................

피보나치 수열는 피보나치가 토끼의 성장과 번식을 관찰하다가 발견한 수열이라고 합니다.

피보나치 수(Fibonacci number)의 정의는 간단합니다.

0과 1로 시작해서 덧셈을 계속 이어가면 얻어지는 수들입니다.

     0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ......

초항을 제 0항으로 하고 제 0항, 제 1항, 제 2항, ...... 순으로 나열하면

    F(0),  F(1),  F(2),  F(3),  F(4), F(5),  F(6),  F(7),  F(8),  F(9),  F(10), ......

이 되고, 번호를 괄호 속에 넣지 않고 우측 첨자로 붙여 나열하면,

    F₀,  F₁,  F₂,  F₃,  F₄,  F₅,  F₆,  F₇,  F₈,  F₉,  F₁₀, ......

이 됩니다.  즉, 

                  F₀ = F(0) = 0

                  F₁ = F(1) = 1

                  F₂ = F(2) = 1

                  F₃ = F(3) = 2

                  F₄ = F(4) = 3

                  F₅ = F(5) = 5

                  F₆ = F(6) = 8

                  F₇ = F(7) = 13

                  F₈ = F(8) = 21

                  F₉ = F(9) = 34

                  F₁₀ = F(10) = 55

                   ........................

피보나치 수들을 점화공식(recurrence formula)으로 정의하면

        F(n) = F(n - 1) + F(n - 2)     ∀ n = 2, 3, 4, 5, ...

        F(0) = 0,  F(1) = 1

가 됩니다.

            0 + 1 = 1

            1 + 1 = 2

            1 + 2 = 3

            2 + 3 = 5

            3 + 5 = 8

            5 + 8 = 13

             ..........

위의 점화공식  F(n) = F(n - 1) + F(n - 2)  은 

               F(n) - F(n - 1) = F(n - 2) 

혹은

               F(n) - F(n - 2) = F(n - 1) 

으로 사용되어지기도 합니다.

Java 에는 부호 없는 native 정수 타입이 없다.

Java 8에 와서야 부호 없는 정수를 처리하기 위한 메서드 몇 개가 추가되었다.

예를 들어, String을 native 타입 number로 변환하는 스태틱 메서드

        Long.parseUnsignedLong(String),  Integer.parseUnsignedint(String),

       Short.parseUnsignedShort(String),  Byte.parseUnsignedByte(String),

들과 역으로 native 타입 number를 String으로 변환하는 스태틱 메서드

        Long.toUnsignedString(long),  Integer.toUnsignedString(int)

가 있는데 이들은 타입 캐스팅할 댸 주의해야 할 부분이 있다.

아래의 Java 소스는 overflow 와 관련하여 심각한 문제가 발생할 수

있음을 보여 준다.

//  Filename: About_Java_Native_Number.java
//
//       Re-consider Java's native numbers (int or long or double) near to theirs maximal valuea
//
//
//  Compile: javac -d . About_Java_Native_Number.java
//  Execute: java About_Java_Native_Number
//
//
// Date: 2023.10.22


public class About_Java_Native_Number
{

    public static void main(String[] args)
    { 
        System.out.printf("What is pow(2, 30) = 2**30 (using Python's integer power operator expression)\n");
        System.out.printf("                   = 1 << 30 (using intege's shift opertor expression)\n");
        System.out.printf("                   = 2^30 (in LaTeX' math expression)\n");
        System.out.printf("\n");

        System.out.printf("Math.pow(2, 30) == %s\n", Math.pow(2, 30));
        System.out.printf("Math.pow(2, 30) == %e\n", Math.pow(2, 30));
        System.out.printf("Math.pow(2, 30) == %.9e\n", Math.pow(2, 30));
        System.out.printf("Math.pow(2, 30) == %g\n", Math.pow(2, 30));
        System.out.printf("Math.pow(2, 30) == %.0g\n", Math.pow(2, 30));
        System.out.printf("Math.pow(2, 30) == %.9g\n", Math.pow(2, 30));
        System.out.printf("Math.pow(2, 30) == %f\n", Math.pow(2, 30));
        System.out.printf("Math.pow(2, 30) == %.0f\n", Math.pow(2, 30));
        System.out.printf("Math.pow(2, 30) == %a\n", Math.pow(2, 30));
        System.out.printf("\n");

        System.out.printf("1 << 30 = %d\n", 1 << 30);
        System.out.printf("(1 << 30) + (1 << 30) = %d\n", (1 << 30) + (1 << 30) );
        System.out.printf("(1 << 30)*2 = %d\n", (1 << 30)*2);
        System.out.printf("1 << (1 << 30) << 1 = %d\n", (1 << 30) << 1 );
        System.out.printf("0x7FFFFFFF = %d\n", 0x7FFFFFFF);
        System.out.printf("0x7FFFFFFF + 1 = %d\n", 0x7FFFFFFF + 1);
        System.out.printf("0x7FFFFFFF + 2 = %d\n", 0x7FFFFFFF + 2);
        System.out.printf("0x7FFFFFFF + 2 = %d\n", 0x7FFFFFFF + 2);
        System.out.printf("0x7FFFFFFF + 1 - 1 = %d\n", 0x7FFFFFFF + 1 - 1);
        System.out.printf("0x7FFFFFFF + 2 - 2 = %d\n", 0x7FFFFFFF + 2 - 2);
        System.out.printf("0x7FFFFFFF + 3 - 3 = %d\n", 0x7FFFFFFF + 3 - 3);
        System.out.printf("\n");

        System.out.printf("Is it true that (0x7FFFFFFF + 1) - 1 = (%d + 1) - 1 = %d - 1 = %d ?\n", 0x7FFFFFFF, 0x7FFFFFFF + 1, (0x7FFFFFFF + 1) - 1);
        System.out.printf("Is it true that (0x7FFFFFFF + 2) - 2 = (%d + 2) - 2 = %d - 2 = %d ?\n", 0x7FFFFFFF, 0x7FFFFFFF + 2, (0x7FFFFFFF + 1) - 2);
        System.out.printf("Is it true that (0x7FFFFFFF + 3) - 3 = (%d + 3) - 3 = %d - 3 = %d ?\n", 0x7FFFFFFF, 0x7FFFFFFF + 3, (0x7FFFFFFF + 1) - 3);
        System.out.printf("\n");

        System.out.printf("It is true that 1 << 30 = %d\n", 1 << 30);
        System.out.printf("But, is it true that (1 << 30)*2/2 = (%d)*2/2 = %d/2 = %d ?\n", 1 << 30, (1 << 30)*2,  (1 << 30)*2/2);
        System.out.printf("And, is it true that (1 << 30)*2/4 = (%d)*2/4 = %d/4 = %d ?\n", 1 << 30, (1 << 30)*2,  (1 << 30)*2/4);
        System.out.printf("And, is it true that (1 << 30)*2/8 = (%d)*2/8 = %d/8 = %d ?\n", 1 << 30, (1 << 30)*2,  (1 << 30)*2/8);
        System.out.printf("\n");

        System.out.printf("Also, is it true that (1 << 30)*4/2 = (%d)*4/2 = %d/2 = %d ?\n", 1 << 30, (1 << 30)*4,  (1 << 30)*4/2);
        System.out.printf("Also, is it true that ((1 << 30)*4 + 1234567)/2 = ((%d)*4 + 1234567)/2 = (%d + 1234567)/2 = %d ?\n", 1 << 30, (1 << 30)*4,  ((1 << 30)*4 + 1234567)/2);
        System.out.printf("Then, is it true that (Math.pow(2, 30)*4 + 1234567)/2 = ((%.0f)*4 + 1234567)/2 = (%.0f + 1234567)/2 = %.0f ?\n", Math.pow(2, 30), Math.pow(2, 30)*4,  (Math.pow(2, 30)*4 + 1234567)/2);


        System.out.printf("In is known that Math.pow(2, 30) == (1 << 30) ? %s\n", Math.pow(2, 30) == (1 << 30));
        System.out.printf("\n");

        System.out.printf("Long.toUnsignedString((byte)0xFFL) = %s\n", Long.toUnsignedString((byte)0xFFL));
        System.out.printf("Long.toUnsignedString(0xFFL) = %s\n", Long.toUnsignedString(0xFFL));
        System.out.printf("Integer.toUnsignedString((byte)0xFFL) = %s\n", Integer.toUnsignedString((byte)0xFFL));
        System.out.printf("Integer.toUnsignedString(0xFF) = %s\n", Integer.toUnsignedString(0xFF));
        System.out.printf("Integer.toUnsignedString(0xFFFFFFFFFF) = %s\n", Integer.toUnsignedString(0xFFFFFFFF));
        System.out.printf("Long.toUnsignedString(0xFFFFFFFFFF) = %s\n", Long.toUnsignedString(0xFFFFFFFF));
        System.out.printf("Long.toUnsignedString(0x100000000L) = %s\n", Long.toUnsignedString(0x100000000L));
        System.out.printf("Long.toUnsignedString(0xFFFFFFFFFFFFFFFFL) = %s\n", Long.toUnsignedString(0xFFFFFFFFFFFFFFFFL));
        System.out.printf("Long.toUnsignedString(0x8000000000000000L) = %s\n", Long.toUnsignedString(0x8000000000000000L));
        System.out.printf("Long.toString(0xFFFFFFFFFFFFFFFFL) = %s\n", Long.toString(0xFFFFFFFFFFFFFFFFL));
        System.out.printf("Long.toString(0x8000000000000000L) = %s\n", Long.toString(0x8000000000000000L));
        System.out.printf("\n");

    }
}

/*
---------
 Output:
---------

What is pow(2, 30) = 2**30 (using Python's integer power operator expression)
                   = 1 << 30 (using intege's shift opertor expression)
                   = 2^30 (in LaTeX' math expression)

Math.pow(2, 30) == 1.073741824E9
Math.pow(2, 30) == 1.073742e+09
Math.pow(2, 30) == 1.073741824e+09
Math.pow(2, 30) == 1.07374e+09
Math.pow(2, 30) == 1e+09
Math.pow(2, 30) == 1.07374182e+09
Math.pow(2, 30) == 1073741824.000000
Math.pow(2, 30) == 1073741824
Math.pow(2, 30) == 0x1.0p30

1 << 30 = 1073741824
(1 << 30) + (1 << 30) = -2147483648
(1 << 30)*2 = -2147483648
1 << (1 << 30) << 1 = -2147483648
0x7FFFFFFF = 2147483647
0x7FFFFFFF + 1 = -2147483648
0x7FFFFFFF + 2 = -2147483647
0x7FFFFFFF + 2 = -2147483647
0x7FFFFFFF + 1 - 1 = 2147483647
0x7FFFFFFF + 2 - 2 = 2147483647
0x7FFFFFFF + 3 - 3 = 2147483647

Is it true that (0x7FFFFFFF + 1) - 1 = (2147483647 + 1) - 1 = -2147483648 - 1 = 2147483647 ?
Is it true that (0x7FFFFFFF + 2) - 2 = (2147483647 + 2) - 2 = -2147483647 - 2 = 2147483646 ?
Is it true that (0x7FFFFFFF + 3) - 3 = (2147483647 + 3) - 3 = -2147483646 - 3 = 2147483645 ?

It is true that 1 << 30 = 1073741824
But, is it true that (1 << 30)*2/2 = (1073741824)*2/2 = -2147483648/2 = -1073741824 ?
And, is it true that (1 << 30)*2/4 = (1073741824)*2/4 = -2147483648/4 = -536870912 ?
And, is it true that (1 << 30)*2/8 = (1073741824)*2/8 = -2147483648/8 = -268435456 ?

Also, is it true that (1 << 30)*4/2 = (1073741824)*4/2 = 0/2 = 0 ?
Also, is it true that ((1 << 30)*4 + 1234567)/2 = ((1073741824)*4 + 1234567)/2 = (0 + 1234567)/2 = 617283 ?
Then, is it true that (Math.pow(2, 30)*4 + 1234567)/2 = ((1073741824)*4 + 1234567)/2 = (4294967296 + 1234567)/2 = 2148100932 ?
In is known that Math.pow(2, 30) == (1 << 30) ? true

Long.toUnsignedString((byte)0xFFL) = 18446744073709551615
Long.toUnsignedString(0xFFL) = 255
Integer.toUnsignedString((byte)0xFFL) = 4294967295
Integer.toUnsignedString(0xFF) = 255
Integer.toUnsignedString(0xFFFFFFFFFF) = 4294967295
Long.toUnsignedString(0xFFFFFFFFFF) = 18446744073709551615
Long.toUnsignedString(0x100000000L) = 4294967296
Long.toUnsignedString(0xFFFFFFFFFFFFFFFFL) = 18446744073709551615
Long.toUnsignedString(0x8000000000000000L) = 9223372036854775808
Long.toString(0xFFFFFFFFFFFFFFFFL) = -1
Long.toString(0x8000000000000000L) = -9223372036854775808
*/