Làm cách nào để đếm số chữ số bằng số trong các căn cứ khác nhau?

Question

Tôi đang làm việc với các số trong các cơ sở khác nhau (base-10, base-8, base-16, v.v.). Tôi đang cố đếm số ký tự trong mỗi số.

Ví dụ

Số: ABCDEF

Số chữ số:

tôi biết về các phương pháp dựa trên logarit nhưng tôi phải đối mặt với một số vấn đề.

1. This Python script kết quả đầu ra không thể tính số chính xác trong 3.969 số trong số 1.000.000.

2. Tôi nghĩ rằng phương pháp sử dụng logarit có thể được khá chậm

Links:

• This C program phải rất chậm (nếu tôi có một số lượng rất lớn?). Nó cũng không thể xử lý các số trong các căn cứ khác nhau (ví dụ, base-16).

• Không phải là một dupe của this như có OP được hỏi chỉ về cơ sở-10

---

Edit: chắc chắn tôi có thể tính toán chiều dài của một chuỗi nhưng những gì tôi quan tâm nhất, là nếu có thể thực hiện phép tính mà không có quy ước đối với chuỗi. Tôi muốn biết thuật toán có thể giúp bạn làm điều đó khi biết chỉ cần nguồn cơ sở và cơ sở để chuyển đổi thành.

Edit2:nguồn-base là cơ số 10 và cơ sở để chuyển đổi sang thể được bất kỳ cơ sở khác.

---

Làm cách nào để tính số chữ số bằng các số khác nhau?

Nếu tôi biết số trong cơ sở-10, làm cách nào để tính số chữ số trong cùng một số được chuyển đổi thành cơ sở-16 (base-8, v.v.) mà không thực hiện chuyển đổi?

Note: một số Python hoặc C mã sẽ được rất nhiều đánh giá cao

Answer 1

Logarit không thực sự chậm. Và bạn có thể dễ dàng tính logarit cho bất kỳ cơ sở nào theo công thức này: logBaseN(x)=logBaseA(x)/logBaseA(N) - bạn có thể sử dụng ln (Cơ sở e = 2.718 ...) hoặc logBase10 hoặc bất kỳ thứ gì bạn có. Vì vậy, bạn không thực sự cần một chương trình, một công thức nên làm điều đó:

num_digets(N, base) = 1 + floor(log(N)/log(base)) 

nơi N là số của bạn và base cơ sở bạn muốn con số trong

Để biết thêm lời giải thích có một cái nhìn ở đây.: http://www.mathpath.org/concepts/Num/numdigits.htm

Answer 2

Tôi không chắc là tôi hiểu câu hỏi của bạn. Khi bạn nói số ban đầu của bạn là trong b1 cơ bản, nó có nghĩa là bạn có một đại diện của nó như là một chuỗi trong b1 cơ sở? Có lẽ bạn muốn xây dựng một số bảng cho bạn biết số nào trong b1 cơ bản tương ứng với b2, b2^2, b2^3, ...và sau đó so sánh số của bạn với những con số này để xem nó phù hợp với đâu.

Nếu không, tôi sẽ đi với thuật toán bạn đã đề cập, có thể dễ dàng áp dụng cho bất kỳ cơ sở nào.

Input: số nguyên của bạn x, cơ sở b2 bạn muốn đếm các chữ số trong

int number_of_digits (int x, int b2) { 
    int n = 0; 
    while (x >0) { 
     x/=b2; 
     n++; 
    } 
    return n; 
} 

Cả hai phương pháp được chỉ tuyến tính trong n..

EDIT: Nếu bạn muốn nhanh hơn, bạn có thể triển khai điều này dưới dạng tìm kiếm nhị phân. Sau đó, bạn có thể nhận được O (log (n)).

Answer 3

Lưu ý NumToStr() chức năng của bạn trong mã Python của bạn là không chính xác do một off-by-one trong cơ sở của bạn, nó phải là:

def NumToStr(num): 
    str='' 
    while num: 
      str+=alpha[(num)%base] 
      num=(num)/base 
    return ''.join(list(reversed(str))) 

Lưu ý rằng việc kiểm tra xem hàm này có trả lại kết quả chính xác hay không sẽ tìm thấy lỗi (ví dụ: sử dụng alpha="").

Với sửa chữa này, chúng ta có được con số chính xác của các chữ số bằng cách sử dụng công thức đưa ra:

nDigits = int(ceil(log(nmb, base))) 

trừ cho quyền hạn chính xác của cơ sở (base**0, base**1, base**2, vv ...) nó ở đâu chính xác một ít hơn những gì nó nên được. Điều này có thể được cố định bằng cách thay đổi forumla nhẹ:

nDigits = 1 + floor(log(nmb, base)) 

Lưu ý rằng ngay cả điều này dường như thất bại đối với một số nguyên liệu đầu vào (ví dụ chuyển đổi từ cơ số 10 căn-10 nó sai nói 3 chữ số cho 1000 và 6 chữ số cho 1000000). Điều này dường như là do inprecision vốn có của nổi, ví dụ:

print floor(log(1000, 10)) 

đầu ra 2 thay vì dự kiến ​​3.

Liên quan đến đề cập đến hiệu suất của bạn, tôi sẽ không lo lắng về các vấn đề về hiệu suất cho mã tầm thường này cho đến khi bạn hoàn thành việc lập hồ sơ/đo điểm chuẩn cho thấy đó là vấn đề. Ví dụ: mã C "rất chậm" của bạn sẽ chỉ mất tối đa 38 đơn vị chia cho 10 cho số 128 bit. Nếu bạn cần hiệu suất tốt hơn so với điều này thì bạn sẽ chạy vào cùng một vấn đề với bất kỳ phương pháp tầm thường nào được đề cập ở đây. Điều nhanh nhất tôi có thể nghĩ sẽ là một hàm log() tùy chỉnh bằng cách sử dụng kết hợp bảng tra cứu và nội suy tuyến tính nhưng bạn sẽ phải cẩn thận về độ chính xác kết quả.