정수의 자릿수 찾기

정수의 자릿수 찾기

---

양의 정수의 자릿수를 찾는 가장 좋은 방법은 무엇입니까?

이 세 가지 기본 방법을 찾았습니다.

• 문자열로 변환

  String s = new Integer(t).toString(); 
  int len = s.length();
  

• for 루프

  for(long long int temp = number; temp >= 1;)
  {
      temp/=10;
      decimalPlaces++;
  } 
  

• 대수 계산

  digits = floor( log10( number ) ) + 1;
  

대부분의 언어에서 log10 (x) = ln (x) / ln (10)을 계산할 수 있습니다.

먼저 스트링 방식이 가장 더럽다고 생각했지만 생각할수록 가장 빠른 방식이라고 생각합니다. 아니면?

---

항상이 방법이 있습니다.

n = 1;
if ( i >= 100000000 ) { n += 8; i /= 100000000; }
if ( i >= 10000     ) { n += 4; i /= 10000; }
if ( i >= 100       ) { n += 2; i /= 100; }
if ( i >= 10        ) { n += 1; }

---

잘 모르겠습니다. 귀하의 개별 언어가 구현되는 방식에 따라 답변이 다를 수 있습니다.

그래서 스트레스 테스트! 세 가지 솔루션을 모두 구현하십시오. 1에서 1,000,000 (또는 솔루션이 실행될 숫자를 나타내는 다른 거대한 숫자 집합)에 대해 실행하고 각각에 걸리는 시간을 측정합니다.

솔루션을 서로 대립하고 싸우게하십시오. 지적 검투사처럼. 3 개의 알고리즘이 들어갑니다! 하나의 알고리즘이 떠납니다!

---

정답은 측정하는 것입니다.하지만 문자열을 변환하고 끝 마커를 찾는 데 관련된 CPU 단계 수를 추측 할 수 있어야합니다.

그런 다음 프로세서가 수행 할 수있는 FPU 작업 / 초 수와 단일 로그 계산이 얼마나 쉬운 지 생각해보십시오.

편집 : 월요일 아침에 더 많은 시간 낭비 :-)

String s = new Integer(t).toString(); 
int len = s.length();

고수준 언어의 문제점 중 하나는 명백하게 단순한 문장 뒤에서 시스템이 얼마나 많은 작업을하고 있는지 추측하는 것입니다. 필수 Joel 링크

이 명령문은 문자열에 대한 메모리 할당과 문자열의 임시 사본 몇 개를 포함합니다. 정수를 구문 분석하고 숫자를 문자열로 복사해야하며, 숫자가 크면 기존 메모리를 재 할당하고 이동해야합니다. 국가가 ","또는 "."를 사용하는지 결정하기 위해 여러 로케일 설정을 확인해야 할 수 있으며, 많은 유니 코드 변환을 수행해야 할 수도 있습니다.
그런 다음 길이를 찾으려면 전체 문자열을 스캔해야합니다. 다시 한 번 유니 코드와-오른쪽-> 왼쪽 언어를 사용하고 있습니까?와 같은 로컬 특정 설정을 고려합니다.

또는 :

digits = floor( log10( number ) ) + 1;

종이로하기가 더 힘들다고해서 컴퓨터가 어렵다는 의미는 아닙니다! 사실 고성능 컴퓨팅의 좋은 규칙은 인간에게 어려운 일 (유체 역학, 3D 렌더링)이 컴퓨터에게는 쉬우 며, 인간에게는 쉬운 일 (얼굴 인식, 음성 감지)이었습니다. 시끄러운 방) 컴퓨터가 어렵다!

일반적으로 내장 된 수학 함수 인 log / sin / cos 등이 50 년 동안 컴퓨터 설계의 중요한 부분이라고 가정 할 수 있습니다. 따라서 FPU의 하드웨어 기능에 직접 매핑되지 않더라도 대체 구현이 매우 효율적이라고 확신 할 수 있습니다.

---

이 알고리즘은 다음과 같은 가정에서도 유용 할 수 있습니다.

• 숫자는 정수이고 이진 인코딩 (<< 연산은 저렴함)

• 우리는 수의 경계를 모릅니다

  var num = 123456789L;
  var len = 0;
  var tmp = 1L;
  while(tmp < num)
  {
      len++;
      tmp = (tmp << 3) + (tmp << 1);
  }
  

이 알고리즘은 제공된 for 루프 (2)와 비슷한 속도를 가져야하지만 (2 비트 시프트, 나누기 대신 더하기 및 빼기)로 인해 조금 더 빠릅니다.

Log10 알고리즘의 경우 Log 함수를 계산하기위한 분석 공식이 무한 루프를 가지고 있으며 정확하게 Wiki를 계산할 수 없기 때문에 대략적인 답만 제공합니다 (실제에 가깝지만 여전히) .

---

시험 조건

• 십진수 체계
• 양의 정수
• 최대 10 자리
• 언어 : 액션 스크립트 3

결과

숫자 : [1,10],

아니. 실행 횟수 : 1,000,000

무작위 샘플 : 8777509,40442298,477894,329950,513,91751410,313,3159,131309,2

결과 : 7,8,6,6,3,8,3,4,6,1

문자열로의 변환 : 724ms

대수 계산 : 349ms

DIV 10 반복 : 229ms

수동 컨디셔닝 : 136ms

참고 : 저자는 10 자리 이상의 숫자에 대해 결론을 내리지 않습니다.

---

스크립트

package {
    import flash.display.MovieClip;
    import flash.utils.getTimer;
    /**
     * @author Daniel
     */
    public class Digits extends MovieClip {
        private const NUMBERS : uint = 1000000;
        private const DIGITS : uint = 10;

        private var numbers : Array;
        private var digits : Array;

        public function Digits() {
            // ************* NUMBERS *************
            numbers = [];
            for (var i : int = 0; i < NUMBERS; i++) {
                var number : Number = Math.floor(Math.pow(10, Math.random()*DIGITS));
                numbers.push(number);
            }   
            trace('Max digits: ' + DIGITS + ', count of numbers: ' + NUMBERS);
            trace('sample: ' + numbers.slice(0, 10));

            // ************* CONVERSION TO STRING *************
            digits = [];
            var time : Number = getTimer();

            for (var i : int = 0; i < numbers.length; i++) {
                digits.push(String(numbers[i]).length);
            }

            trace('\nCONVERSION TO STRING - time: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));

            // ************* LOGARITMIC CALCULATION *************
            digits = [];
            time = getTimer();

            for (var i : int = 0; i < numbers.length; i++) {
                digits.push(Math.floor( Math.log( numbers[i] ) / Math.log(10) ) + 1);
            }

            trace('\nLOGARITMIC CALCULATION - time: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));

            // ************* DIV 10 ITERATION *************
            digits = [];
            time = getTimer();

            var digit : uint = 0;
            for (var i : int = 0; i < numbers.length; i++) {
                digit = 0;
                for(var temp : Number = numbers[i]; temp >= 1;)
                {
                    temp/=10;
                    digit++;
                } 
                digits.push(digit);
            }

            trace('\nDIV 10 ITERATION - time: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));

            // ************* MANUAL CONDITIONING *************
            digits = [];
            time = getTimer();

            var digit : uint;
            for (var i : int = 0; i < numbers.length; i++) {
                var number : Number = numbers[i];
                if (number < 10) digit = 1;
                else if (number < 100) digit = 2;  
                else if (number < 1000) digit = 3;  
                else if (number < 10000) digit = 4;  
                else if (number < 100000) digit = 5;  
                else if (number < 1000000) digit = 6;  
                else if (number < 10000000) digit = 7;  
                else if (number < 100000000) digit = 8;  
                else if (number < 1000000000) digit = 9;  
                else if (number < 10000000000) digit = 10;  
                digits.push(digit);
            }

            trace('\nMANUAL CONDITIONING: ' + (getTimer() - time));
            trace('sample: ' + digits.slice(0, 10));
        }
    }
}

---

• 문자열로 변환 : 각 숫자를 반복하고 현재 숫자에 매핑되는 문자를 찾고 문자 모음에 문자를 추가해야합니다. 그런 다음 결과 String 객체의 길이를 가져옵니다. n = # digits에 대해 O (n)에서 실행됩니다.

• for-loop : 두 가지 수학적 연산을 수행합니다 : 숫자를 10으로 나누고 카운터를 증가시킵니다. n = # digits에 대해 O (n)에서 실행됩니다.

• logarithmic : log10과 floor를 호출하고 1을 더합니다. O (1)처럼 보이지만 log10 또는 floor 함수가 얼마나 빠른지 잘 모르겠습니다. 이런 종류의 일에 대한 나의 지식은 사용 부족으로 위축 되어 이러한 기능에 숨겨진 복잡성 이있을 수 있습니다 .

그래서 나는 그것이 다음과 같은 것이라고 생각합니다 : 여러 수학 연산보다 더 빨리 숫자 매핑을 찾고 log10있습니까? 대답은 아마도 다를 것입니다. 캐릭터 매핑이 더 빠른 플랫폼과 계산이 더 빠른 플랫폼이있을 수 있습니다. 또한 염두에 두어야 할 것은 첫 번째 메소드는 길이를 얻기위한 목적으로 만 존재하는 새로운 String 객체를 생성한다는 것입니다. 이것은 아마도 다른 두 가지 방법보다 더 많은 메모리를 사용하지만 중요 할 수도 있고 중요하지 않을 수도 있습니다.

---

사용하는 atoi / toString 알고리즘이 방법 2와 유사하기 때문에 경쟁에서 방법 1을 제거 할 수 있습니다.

방법 3의 속도는 명령어 세트에 log base 10이 포함 된 시스템에 대해 코드가 컴파일되고 있는지 여부에 따라 다릅니다.

---

사용중인 프로그래밍 언어에 상관없이 가장 간단한 솔루션을 사용하십시오. 정수로 숫자를 세는 것이 (유용한) 프로그램에서 병목 현상이되는 경우를 생각할 수 없습니다.

C, C ++ :

char buffer[32];
int length = sprintf(buffer, "%ld", (long)123456789);

Haskell :

len = (length . show) 123456789

자바 스크립트 :

length = String(123456789).length;

PHP :

$length = strlen(123456789);

Visual Basic (예상되지 않음) :

length = Len(str(123456789)) - 1

---

매우 큰 정수의 경우 로그 방법이 훨씬 빠릅니다. 예를 들어 2491327 자리 숫자 (관심이 있다면 11920928 번째 피보나치 숫자)를 사용하면 Python은 10으로 나누기 알고리즘을 실행하는 데 몇 분이 걸리고 실행하는 데 밀리 초가 걸립니다 1+floor(log(n,10)).

---

import math
def numdigits(n):
    return ( int(math.floor(math.log10(n))) + 1 )

---

"주어진 밑수에서 주어진 숫자를 표현하는 데 필요한 자릿수 결정"을 위해 제안한 세 가지 방법에 관해서는 실제로 그 중 어느 것도 좋아하지 않습니다. 대신 아래에 제공하는 방법을 선호합니다.

방법 # 1 (문자열) : 문자열과 숫자 사이의 앞뒤로 변환하는 작업은 일반적으로 매우 느립니다.

방법 # 2 (temp / = 10) : x / 10은 항상 "x를 10으로 나누기"를 의미한다고 가정하기 때문에 이것은 치명적인 결함입니다. 그러나 많은 프로그래밍 언어 (예 : C, C ++)에서 "x"가 정수 유형이면 "x / 10"은 "정수 나눗셈"을 의미합니다. 이는 부동 소수점 나눗셈과 동일하지 않습니다. 반복 할 때마다 반올림 오류가 발생하며 솔루션 # 2에서 사용하는 것과 같은 반복 공식에 누적됩니다.

방법 # 3 (로그) : 부동 소수점 데이터 유형이 64 비트 정수만큼 정확하지 않은 경향이 있기 때문에 큰 숫자 (적어도 C 및 다른 언어에서도 가능)의 경우 버그가 있습니다.

따라서 저는이 세 가지 방법을 모두 싫어합니다. # 1은 작동하지만 느리고 # 2는 고장 났으며 # 3은 많은 수의 경우 버그가 있습니다. 대신 0에서 약 18.44 quintillion까지의 숫자에 대해 작동하는 이것을 선호합니다.

unsigned NumberOfDigits (uint64_t Number, unsigned Base)
{
   unsigned Digits = 1;
   uint64_t Power  = 1;
   while ( Number / Power >=  Base )
   {
      ++Digits;
      Power *= Base;
   }
   return Digits;
}

---

간단하게 유지 :

long long int a = 223452355415634664;

int x;
for (x = 1; a >= 10; x++)
{
   a = a / 10;
}

printf("%d", x);

---

루프 대신 재귀 솔루션을 사용할 수 있지만 어떻게 든 비슷합니다.

@tailrec
def digits (i: Long, carry: Int=1) : Int =  if (i < 10) carry else digits (i/10, carry+1)

digits (8345012978643L)

long을 사용하면 그림이 변경 될 수 있습니다. 서로 다른 알고리즘에 대해 독립적으로 작고 긴 숫자를 측정하고 일반적인 입력에 따라 적절한 숫자를 선택합니다. :)

물론 스위치를 능가하는 것은 없습니다.

switch (x) {
  case 0:  case 1:  case 2:  case 3:  case 4:  case 5:  case 6:  case 7:  case 8:  case 9: return 1;
  case 10: case 11: // ...
  case 99: return 2;
  case 100: // you get the point :) 
  default: return 10; // switch only over int
}

일반 배열 제외 :

   int [] size = {1,1,1,1,1,1,1,1,1,2,2,2,2,2,... };
   int x = 234561798;
   return size [x];

어떤 사람들은 코드 크기를 최적화하라고 말할 것입니다. 그러나 아시다시피, 조기 최적화 ...

---

다음은 Swift 4의 측정입니다.

알고리즘 코드 :

extension Int {
    var numberOfDigits0: Int {
        var currentNumber = self
        var n = 1
        if (currentNumber >= 100000000) {
            n += 8
            currentNumber /= 100000000
        }
        if (currentNumber >= 10000) {
            n += 4
            currentNumber /= 10000
        }
        if (currentNumber >= 100) {
            n += 2
            currentNumber /= 100
        }
        if (currentNumber >= 10) {
            n += 1
        }
        return n
    }

    var numberOfDigits1: Int {
        return String(self).count
    }

    var numberOfDigits2: Int {
        var n = 1
        var currentNumber = self
        while currentNumber > 9 {
            n += 1
            currentNumber /= 10
        }
        return n
    }

}

측정 코드 :

var timeInterval0 = Date()
for i in 0...10000 {
    i.numberOfDigits0
}
print("timeInterval0: \(Date().timeIntervalSince(timeInterval0))")

var timeInterval1 = Date()
for i in 0...10000 {
    i.numberOfDigits1
}
print("timeInterval1: \(Date().timeIntervalSince(timeInterval1))")

var timeInterval2 = Date()
for i in 0...10000 {
    i.numberOfDigits2
}
print("timeInterval2: \(Date().timeIntervalSince(timeInterval2))")

산출

timeInterval0 : 1.92149806022644

timeInterval1 : 0.557608008384705

timeInterval2 : 2.83262193202972

이 측정 기준에서 문자열 변환은 Swift 언어에 가장 적합한 옵션입니다.

---

@ daniel.sedlacek 결과를보고 궁금해서 10 자리가 넘는 숫자에 대해 Swift를 사용하여 테스트했습니다. 놀이터에서 다음 스크립트를 실행했습니다.

let base = [Double(100090000000), Double(100050000), Double(100050000), Double(100000200)]
var rar = [Double]()
for i in 1...10 {
    for d in base {
        let v = d*Double(arc4random_uniform(UInt32(1000000000)))
        rar.append(v*Double(arc4random_uniform(UInt32(1000000000))))
        rar.append(Double(1)*pow(1,Double(i)))
    }
}

print(rar)

var timeInterval = NSDate().timeIntervalSince1970

for d in rar {
    floor(log10(d))
}

var newTimeInterval = NSDate().timeIntervalSince1970

print(newTimeInterval-timeInterval)


timeInterval = NSDate().timeIntervalSince1970
for d in rar {
    var c = d
    while c > 10 {
        c = c/10
    }
}

newTimeInterval = NSDate().timeIntervalSince1970

print(newTimeInterval-timeInterval)

80 개 요소의 결과

0.105069875717163 for floor(log10(x))
0.867973804473877 for div 10 iterations

---

log(x,n)-mod(log(x,n),1)+1

Where x is a the base and n is the number.

ReferenceURL : https://stackoverflow.com/questions/6655754/finding-the-number-of-digits-of-an-integer