Burt.K

코코아를 좋아하는 프로그래머입니다 ;)

Swift로 아주 큰 수를 곱해 보자.

Swift로 큰 수를 곱해보자. 이를테면,

123456789123456789012345678912345678901234567891234567890123456789123456789012
345678912345678901234567891234567890123456789123456789012345678912345678901234
56789123456789012345678901234567890123456789
 * 
123456789123456789012345678912345678901234567891234567890123456789123456789012
345678912345678901234567891234567890123456789123456789012345678912345678901234
56789123456789012345678901234567890123456789

같은 수를 곱해보자. 

Swift에서 큰 수를 표현하기 위해 사용할 수 있는 데이터 타입은 UInt64, Double 그리고 NSDecimalNumber이다. 그러나 아주 큰 정수를 표현하기에는 부족한 면이 있다. 물론 Github에 보면 BigInteger를 위한 프로젝트들이 있다.

  • https://github.com/BitBaum/Swift-Big-Integer
  • https://github.com/githotto/osxgmp
  • https://github.com/kirsteins/BigInteger
  • 여기서는 위의 프로젝트 코드를 사용하지 않고 문자열로 큰 정수를 전달하면 곱셈 후 다시 문자열로 반환하는 함수를 작성해 보자. 그냥 재미로 🙂 재미로 하는 것이기에 메모리도 아주 왕창 사용할 것이다. 🙂

    우선 문자열의 수를 받으면 각 자리수를 정수로 변환해 리스트로 만든다.

    “1234” -> [1,2,3,4] 로 변환하는 것이다. “1234” * “1234” 는 [1,2,3,4] * [1,2,3,4] 로 변경해 계산한다. 각 문자열을 정수 리스트로 변경해야 하기 때문에 리스트 생성에 따른 메모리가 숫자 N의 길이에 비례해 증가한다.

    우선 곱셈을 생각해 보자.

      5678
     *  23
    -------
     17034
    11356
    -------
    130594

    보통 우리는 이렇게 계산한다. 위의 17034, 113560, 130594 등을 계산할 때 우리는 자리수 올림과 같은 많은 계산을 머리속에서 하고 하나의 결과로 함축하여 나타낸다. 이것을 함축하지 않고 나타내면 아래와 같다.

              5678
              * 23
    --------------
       15 18 21 24
    10 12 14 16
    --------------
    10 27 32 37 24

    위의 10 27 32 37 24 는 아직 자리수 올림을 하지 않은 결과이다. 이제 자리수 올림을 해 보자.

    제일 끝자리수 24는 일의 자리수로 20은 앞의 십의 자리수로 넘겨줘야 한다. 십의 자리수는 앞의 37 중 7이다. 그래서 37 24 가 394가 된다. 이렇게 자리수를 계속 넘겨 주면 아래처럼 결과가 생긴다.

    10 27 32 37 24
    --------------
      10 27 32 394
        10 27 3594
          10 30594
            130594

    처음에 자리수올림을 함축하여 계산한 결과와 같아졌다. 이 방법을 그대로 사용하면 된다. 그래서 문자열을 자리수 기준으로 나눠 정수 목록으로 만든 것이다.

    "5678" * "23" 
    = [5,6,7,8] * [2,3]
    = [10,27,32,37,24]

    이렇게 곱하는 코드를 swift로 표현하면 아래와 같다.

    func multiplyList(a : [Int], _ b:[Int]) -> [Int] {
        var result : [Int] = Array(count: a.count + b.count - 1, repeatedValue: 0)
    
        for i in 0..<a.count {
            for j in 0..<b.count {
                result[i+j] += a[i] * b[j]
            }
        }
        return result
    }

    목록을 곱한 후 해야할 일은 자리수 올림을 해서 최종결과를 얻는 것이다.

    즉, [10,27,32,36,24]를 [1,3,0,5,9,4] 로 변경한다.

    func nomalize(n : [Int]) -> [Int] {
        // mutable copy
        var result : [Int] = n
        
        for var i = n.count-1 ; i>0; i-- {
            
            //[16, 12] 
            //가 있으면 
            //12를 %10 하여 2를 남기고
            //12를 /10 하여 1을 앞자리수 인 16에 더한다
            //[17, 2]
            //이런식으로 계속 간다
            result[i-1] = result[i-1] + result[i] / 10
            result[i] = result[i] % 10
        }
    
        return result
    }
    

    [1,3,0,5,9,4] 를 얻은 후 리스트를 문자열로 변경하는 코드는 아래와 같다.

    func convertListToString(n: [Int]) -> String {
        return n.map {
            "\($0)"
        }.joinWithSeparator("")
    }

    위의 함수를 적용하면 “130594” 를 얻을 수 있다.

    전체 코드를 적어보면 아래와 같다.

    func multiplyList(a : [Int], _ b:[Int]) -> [Int] {
        var result : [Int] = Array(count: a.count + b.count - 1, repeatedValue: 0)
    
        for i in 0..<a.count {
            for j in 0..<b.count {
                result[i+j] += a[i] * b[j]
            }
        }
        return result
    }
    
    func nomalize(n : [Int]) -> [Int] {
        // mutable copy
        var result : [Int] = n
        
        for var i = n.count-1 ; i>0; i-- {
            
            //[16, 12] 
            //가 있으면 
            //12를 %10 하여 2를 남기고
            //12를 /10 하여 1을 앞자리수 인 16에 더한다
            //[17, 2]
            //이런식으로 계속 간다
            result[i-1] = result[i-1] + result[i] / 10
            result[i] = result[i] % 10
        }
    
        return result
    }
    
    func convertListToString(n: [Int]) -> String {
        return n.map {
            "\($0)"
        }.joinWithSeparator("")
    }
    
    func multiply(a: String, _ b: String) -> String {
        
        guard a.characters.count > 0 || b.characters.count > 0 else {
            return "Error"
        }
        
        var aList : [Int] = []
        var bList : [Int] = []
        
        for ch in a.characters {
            aList.append(Int(String(ch))!)
        }
        
        for ch in b.characters {
            bList.append(Int(String(ch))!)
        }
        
        
        return convertListToString(nomalize( multiplyList(aList, bList)))
    }

    이제 아래의 수를 곱해보자.

    123456789123456789012345678912345678901234567891234567890123456789123456789012
    345678912345678901234567891234567890123456789123456789012345678912345678901234
    56789123456789012345678901234567890123456789
     * 
    123456789123456789012345678912345678901234567891234567890123456789123456789012
    345678912345678901234567891234567890123456789123456789012345678912345678901234
    56789123456789012345678901234567890123456789
    
    multiply(
    "123456789123456789012345678912345678901234567891234567890123456789
    123456789012345678912345678901234567891234567890123456789123456789012345678912
    34567890123456789123456789012345678901234567890123456789"
     ,
    "123456789123456789012345678912345678901234567891234567890123456789
    123456789012345678912345678901234567891234567890123456789123456789012345678912
    34567890123456789123456789012345678901234567890123456789")
    
    ==
    
    152415787806736785186709365063252567035817715134583145555296449376284103440701
    112723910989232587258051019356812110440482964761470096215516082758725898138698
    386904130478665584516552964488333924706804267337406825362005998475851830821522
    737021796297910684487419600741273921670113702185275677489148544429642396281128
    571864075722481334228928518720533455560067062987005334557625361987875019051998
    750190521

    아주 비효율적이지만 결과를 얻긴했다ㅋ. 이글의 결론은? Swift에 이렇게 큰 수를 연산할 수 있는 내장타입이 있었으면 좋겠다 🙂

     

    ← 대수적 데이터 타입과 Enum
    멋쟁이 헤스켈, List Comprehension! →