Matematika di balik konversi dari basis ke basis tanpa melalui basis 10?

36

Saya telah melihat ke dalam matematika di balik konversi dari basis apa pun ke basis apa pun. Ini lebih tentang mengonfirmasi hasil saya daripada apa pun. Saya menemukan apa yang tampaknya menjadi jawaban saya di mathforum.org tetapi saya masih tidak yakin apakah saya benar. Saya memiliki konversi dari basis yang lebih besar ke basis yang lebih kecil oke karena hanya mengambil digit pertama dengan basis Anda ingin menambahkan pengulangan digit berikutnya. Masalah saya muncul saat mengkonversi dari basis yang lebih kecil ke basis yang lebih besar. Ketika melakukan ini mereka berbicara tentang bagaimana Anda perlu mengubah basis yang lebih besar yang Anda inginkan menjadi basis yang lebih kecil yang Anda miliki. Sebuah contoh akan pergi dari basis 4 ke basis 6 Anda perlu mengubah angka 6 menjadi basis 4 mendapatkan 12. Anda kemudian hanya melakukan hal yang sama seperti yang Anda lakukan ketika Anda mengkonversi dari besar ke kecil. Kesulitan yang saya miliki dengan ini adalah sepertinya Anda perlu tahu nomor apa yang ada di pangkalan lainnya. Jadi saya perlu tahu apa yang ada di dasar 4. Ini menciptakan masalah besar dalam pikiran saya karena saya akan membutuhkan sebuah tabel. Adakah yang tahu cara melakukan ini dengan cara yang lebih baik.

Saya pikir konversi basis akan membantu tetapi saya tidak dapat menemukan yang berfungsi. Dan dari situs yang saya temukan tampaknya memungkinkan Anda untuk mengkonversi dari basis ke basis tanpa melalui basis 10 tetapi Anda harus terlebih dahulu tahu cara mengubah angka pertama dari basis ke basis. Itu membuatnya agak tidak berguna.

Para komentator mengatakan bahwa saya harus dapat mengubah huruf menjadi angka. Kalau begitu saya sudah tahu itu. Namun itu bukan masalah saya. Masalah saya adalah untuk mengkonversi basis besar ke basis kecil saya harus terlebih dahulu mengkonversi nomor basis yang saya miliki ke nomor basis yang saya inginkan. Dalam melakukan ini saya mengalahkan tujuannya karena jika saya memiliki kemampuan untuk mengubah basis-basis ini ke basis-basis lain, saya sudah menyelesaikan masalah saya.

Sunting: Saya telah menemukan cara untuk mengkonversi dari basis kurang dari atau sama dengan 10 ke basis lain kurang dari atau sama dengan 10. Saya juga bisa beralih dari basis lebih besar dari 10 ke basis apa pun yang 10 atau kurang. Masalahnya dimulai ketika mengkonversi dari basis lebih besar dari 10 ke basis lain lebih besar dari 10. Atau pergi dari basis lebih kecil dari 10 ke basis lebih besar dari 10. Saya tidak perlu kode Saya hanya perlu matematika dasar di belakangnya yang dapat diterapkan pada kode.

Grifon
sumber
1
Apakah ini pertanyaan tentang topik untuk forum ini?
Andrej Bauer
2
Prosedurnya sepele selama Anda bisa melakukan penambahan dan perkalian di basis target. Jika Anda tidak bisa, saya pikir itu tidak mungkin.
Karolis Juodelė
9
Griffin pertama-tama harus diberi tahu apa yang perlu didengar banyak siswa: angka ada tanpa diwakili dalam basis . Maka jawabannya jelas: kita perlu algoritma, satu untuk mengubah representasi angka dalam basis tertentu ke angka (yaitu, sesuatu yang mengambil stringdan mengembalikan a int), dan algoritma yang mengambil angka dan mengembalikan perwakilannya di basis yang diberikan.
Andrej Bauer
1
@AndrejBauer Pertanyaannya adalah tentang CS: meskipun tidak seperti itu, ini adalah pertanyaan tentang algoritma untuk mengkonversi antara representasi angka. [Catatan yang tidak terkait: Saya menghapus banyak komentar yang membingungkan. Griffin: silakan edit pertanyaan Anda untuk memperbaruinya. Lainnya: tolong bawa untuk ngobrol .]
Gilles 'SO- stop being evil'
1
@ Griffin sudah lama sejak pertanyaan awal Anda. Saya harap Anda menemukan jawaban Anda. Jika demikian, mungkin ini merupakan ide bagus untuk memperbarui dan menerima jawaban atau memposting jawaban Anda. Sementara itu saya telah menemukan beberapa ide yang sangat bagus (berbicara tentang implementasi dalam C ++) di Arsip Code Jam Google. Beberapa solusi untuk masalah ini adalah code.google.com/codejam/contest/32003/dashboard
IsaacCisneros

Jawaban:

45

Ini sepertinya pertanyaan yang sangat mendasar bagi saya, jadi maafkan saya jika saya sedikit menguliahi Anda. Poin terpenting bagi Anda untuk belajar di sini adalah bahwa angka bukanlah representasi digitnya . Angka adalah objek matematika abstrak, sedangkan representasi digitnya adalah hal yang konkret, yaitu urutan simbol pada kertas (atau urutan bit dalam memori komputasi, atau urutan suara yang Anda buat saat Anda berkomunikasi angka). Yang membingungkan Anda adalah kenyataan bahwa Anda tidak pernah melihat angka tetapi selalu mewakili digitnya. Jadi Anda akhirnya berpikir bahwa angka adalah representasi.

Oleh karena itu, pertanyaan yang tepat untuk ditanyakan bukanlah "bagaimana saya mengkonversi dari satu basis ke basis lainnya" melainkan "bagaimana cara mencari tahu nomor mana yang diwakili oleh serangkaian angka" dan "bagaimana cara menemukan representasi digit dari suatu basis diberikan nomor ".

Jadi mari kita menghasilkan dua fungsi dalam Python, satu untuk mengubah representasi digit ke angka, dan yang lainnya untuk melakukan yang sebaliknya. Catatan: ketika kita menjalankan fungsi Python tentu saja akan mencetak pada layar nomor yang didapatnya di basis 10. Tapi ini tidak berarti bahwa komputer menyimpan angka di basis 10 (bukan). Tidak relevan bagaimana komputer merepresentasikan angka.

def toDigits(n, b):
    """Convert a positive number n to its digit representation in base b."""
    digits = []
    while n > 0:
        digits.insert(0, n % b)
        n  = n // b
    return digits

def fromDigits(digits, b):
    """Compute the number given by digits in base b."""
    n = 0
    for d in digits:
        n = b * n + d
    return n

Mari kita uji ini:

>>> toDigits(42, 2)
[1, 0, 1, 0, 1, 0]
>>> toDigits(42, 3)
[1, 1, 2, 0]
>>> fromDigits([1,1,2,0],3)
42

Dipersenjatai dengan fungsi konversi, masalah Anda diselesaikan dengan mudah:

def convertBase(digits, b, c):
    """Convert the digits representation of a number from base b to base c."""
    return toDigits(fromDigits(digits, b), c)

Sebuah tes:

>>> convertBase([1,1,2,0], 3, 2) 
[1, 0, 1, 0, 1, 0]

Catatan: kami tidak melewati representasi basis 10! Kami mengonversi representasi basis ke angka, dan kemudian angka ke basis c . Jumlah itu tidak ada dalam representasi apa pun. (Sebenarnya itu adalah, komputer harus mewakilinya entah bagaimana, dan itu memang mewakilinya menggunakan sinyal listrik dan hal-hal funky yang terjadi dalam chip, tetapi tentu saja itu bukan 0 dan 1.)bc

Andrej Bauer
sumber
4
Ini tidak meyakinkan saya 100%. Faktanya, Anda memang mengonversi angka menjadi beberapa representasi (walaupun Anda dapat mengklaim tidak tahu apa itu) karena komputer bukan ahli matematika platonik dan algoritma Anda tidak dapat mengonversi urutan angka acak dalam basis ke basis b 2 ; itu hanya dapat mengubah urutan yang diwakili oleh mesin beton. Python sangat fleksibel; C tidak akan begitu memaafkan. Sangat valid untuk bertanya bagaimana mengkonversi string arbitrer dari b 1 ke b 2 ; namun, ini hanya mungkin dalam waktu linier kecuali dengan kombinasi basa tertentu (mis. 2 <-> 16)b1b2b1b2
rici
1
Adalah sah untuk mengajukan pertanyaan, tetapi untuk menemukan jawaban yang tepat yang terbaik adalah menyadari fakta bahwa angka adalah entitas abstrak.
Andrej Bauer
2
Ini memang melewati angka melalui representasi basis 10, karena fromDigitsmengembalikan angka di basis 10.
apnorton
8
@ortort: ​​Tidak, pasti tidak . Python mencetak angka di layar dalam basis 10 digit representasi, tetapi nomor itu sendiri tidak disimpan dengan cara itu. Apa yang saya coba sampaikan adalah bahwa tidak relevan bagaimana angka-angka tersebut diimplementasikan dalam Python. Tidak masalah. Satu-satunya hal yang penting adalah mereka berperilaku seperti angka.
Andrej Bauer
3
Akhirnya solusi umum untuk basis apa pun dan tidak terbatas pada kasus penggunaan tertentu, basis kurang dari 36, atau contoh di mana Anda dapat menemukan simbol unik yang cukup.
J.Money
21

Saya pikir cara terbaik untuk memahami ini adalah dalam diskusi dengan alien (setidaknya sebagai analogi).

Definisi adalah angka dalam basis bxb berarti adalah serangkaian digitx .<b

Contoh String angka 10010011011 adalah angka dalam basis 2, string 68416841531 adalah angka di basis 10, BADCAFE adalah angka di basis 16.

Sekarang Misalkan saya dibesarkan di planet QUUX di mana setiap orang diajarkan untuk bekerja di q selama hidup mereka, dan saya bertemu Anda yang terbiasa dengan . Jadi, Anda menunjukkan nomor, dan apa yang harus saya lakukan? Saya perlu cara untuk menafsirkannya:b

Definisi Saya dapat menginterpretasikan angka dalam basis (Catatan: b adalah angka dalam basis qbbq ) dengan rumus berikut

[[ϵ]]=0[[s¯d]]=[[s¯]]×b+d

di mana menunjukkan string kosong, dan ˉ s d Menandakan string berakhir di digit dϵs¯dd . Lihat bukti saya bahwa penambahan menambahkan untuk pengantar notasi ini.

Jadi apa yang terjadi di sini? Anda telah memberi saya nomor dalam basis dan saya telah menafsirkannya menjadi basis q tanpa filosofi aneh tentang apa sebenarnya angka itu.bq

Kunci Kunci untuk ini adalah bahwa fungsi dan + I adalah yang beroperasi pada basis q number. Ini adalah algoritma sederhana yang didefinisikan secara rekursif berdasarkan nomor q basis (string digit).×+qq


Ini mungkin tampak agak abstrak karena saya telah menggunakan variabel daripada angka aktual di seluruh. Jadi anggaplah Anda adalah makhluk basis 13 (menggunakan simbol ) dan saya terbiasa dengan basis 7 (yang jauh lebih masuk akal) menggunakan simbol α β γ δ δ ρ ζ0123456789XYZαβγδρζξ

Jadi saya telah melihat alfabet Anda dan menabunya sebagai berikut:

0α1β2γ3δ4ρ5ζ6ξ7βα8ββ9βγXβδYβρZβζ

βξ

60Z8

[[60Z8]]=ξ(βξ)3+α(βξ)2+βζ(βξ)+ββ

βζ×βξ

Tabel perkalian quux

×βγδρζξββγδρζξγγρξβββδβζδδξβγβζγβγρρρβββζγγγξδδζζβδγβγξδρργξξβζγρδδργζββαβαγαδαραζαξα

βζ×βξ

βζ×βξξγρβζδβγγ

jadi saya sudah sejauh ini

[[60Z8]]=ξ(βξ)3+α(βξ)2+βζ(βξ)+ββ=ξ(βξ)3+α(βξ)2+δβγ+ββ

Sekarang saya perlu melakukan penambahan menggunakan algoritma yang disebutkan sebelumnya:

δβγββδγδ

begitu

[[60Z8]]=ξ(βξ)3+α(βξ)2+βζ(βξ)+ββ=ξ(βξ)3+α(βξ)2+δβγ+ββ=ξ(βξ)3+α(βξ)2+δγδ

[[60Z8]]=ζδξγρ.

qbq

Kadal diskrit
sumber
1
Yah itu banyak garis berlekuk-lekuk. Bagaimana saya bisa membuat komputer melakukan itu?
Griffin
1
@ Griffin, saya pikir Anda menanyakan pertanyaan (aneh) sebelum waktunya. Anda memilih bahasa pemrograman dan mengetik algoritma untuk penambahan dan perkalian pada nomor q basis (diwakili sebagai daftar angka), lalu tentukan fungsi untuk menginterpretasikan angka dasar b menjadi angka dasar q dan menafsirkan angka dasar b menjadi angka dasar q. Saya sudah menjelaskan semua ini.
Masalahnya saya tahu konsep yang Anda coba gambarkan. Masalah saya adalah komputer saya tidak dapat menggunakan garis berlekuk-lekuk Anda.
Griffin
Saya tahu apa yang Anda jelaskan tetapi mempraktikkannya jauh lebih sulit. Anda melihat mendefinisikan angka-angka itu tidak mudah.
Griffin
1
Juga mengapa Anda menjatuhkan digit alpha di posisi paling signifikan? Karena 6 = & xi ;, Bukankah 7 = & alpha; & alpha ;?
Giovanni Botta
9

Ini hanya refactoring (Python 3) dari kode Andrej . Dalam kode Andrej nomor diwakili melalui daftar digit (skalar), sedangkan dalam kode berikut nomor diwakili melalui daftar simbol yang diambil dari string khusus :

def v2r(n, base): # value to representation
    """Convert a positive number to its digit representation in a custom base."""
    b = len(base)
    digits = ''
    while n > 0:
        digits = base[n % b] + digits
        n  = n // b
    return digits

def r2v(digits, base): # representation to value
    """Compute the number represented by string 'digits' in a custom base."""
    b = len(base)
    n = 0
    for d in digits:
        n = b * n + base[:b].index(d)
    return n

def b2b(digits, base1, base2):
    """Convert the digits representation of a number from base1 to base2."""
    return v2r(r2v(digits, base1), base2)

Untuk melakukan konversi dari nilai ke representasi di basis kustom:

>>> v2r(64,'01')
'1000000'
>>> v2r(64,'XY')
'YXXXXXX'
>>> v2r(12340,'ZABCDEFGHI') # decimal base with custom symbols
'ABCDZ'

Untuk melakukan konversi dari representasi (dalam basis khusus) ke nilai:

>>> r2v('100','01')
4
>>> r2v('100','0123456789') # standard decimal base
100
>>> r2v('100','01_whatevr') # decimal base with custom symbols
100
>>> r2v('100','0123456789ABCDEF') # standard hexadecimal base
256
>>> r2v('100','01_whatevr-jklmn') # hexadecimal base with custom symbols
256

Untuk melakukan konversi basis dari satu basis pelanggan ke yang lain:

>>> b2b('1120','012','01')
'101010'
>>> b2b('100','01','0123456789')
'4'
>>> b2b('100','0123456789ABCDEF','01')
'100000000'
mmj
sumber
1
Selamat datang di situs ini dan terima kasih atas kontribusi Anda. Namun, menghasilkan kode sumber yang dioptimalkan dengan baik bukanlah tentang situs ini sebenarnya. Kode Andrej membuat konsep menjadi jelas, yang merupakan apa yang diperlukan untuk jawabannya, tetapi meningkatkan kode di luar itu adalah masalah pemrograman, bukan ilmu komputer .
David Richerby
1
@ DavidVicherby Saya sebagian setuju, tetapi kontribusi ini terlalu panjang untuk komentar dan tempat terbaik untuk berada di suatu tempat dekat jawaban Andrej, itu sebabnya saya diposting di sini. Ngomong-ngomong, jika Anda pikir lebih baik saya bisa mengonversinya menjadi komentar dengan tautan ke kode tersebut, tetapi bukankah ini akan menjadi kemurnian yang berlebihan?
mmj
1

Operasi mendasar dari konversi basis adalah toDigits() operasi jawaban @AndrejBauer. Namun, untuk membuatnya tidak perlu membuat angka dalam representasi internal angka, yang pada dasarnya merupakan konversi dari dan ke basis 2 representasi. Anda dapat membuat operasi yang diperlukan dalam representasi basis asli.

Jadi langkah pertama adalah melakukan operasi divisi modulo berulang

def convertBase(n,original_base,destination_base):
    digits = []    
    while not is_zero(n):
        digits.insert(0,modulo_div(n,original_base,destination_base))
    return digits

Karena representasi internal adalah digit, kita harus membuat fungsi khusus untuk menguji nol

def is_zero(n):
    for d in n:
        if d != 0:
            return False
    return True

Akhirnya kita harus membuat operasi modulo_div yang sebenarnya merupakan pembagian standar berdasarkan tujuan seperti yang kita pelajari di sekolah.

def modulo_div(n,original_base,destination_base):
    carry = 0
    for i in range(len(n)):
        d = n[i]
        d+=original_base*carry 
        carry = d%destination_base 
        d=(d//destination_base)
        n[i] = d
        #print(i,d,carry)
    return carry

hanya pemeriksaan tes untuk memverifikasi kode sudah benar:

print(convertBase([1,1,2,0], 3, 2))
#[1, 0, 1, 0, 1, 0]

print(convertBase([1, 0, 1, 0, 1, 0], 2, 3))
#[1, 1, 2, 0]
Xavier Combelle
sumber
Terima kasih telah memposting, tetapi harap dicatat bahwa kami bukan situs pengkodean, jadi blok kode yang besar tidak sesuai sebagai jawaban di sini. Terutama ketika pertanyaan secara eksplisit mengatakan, "Saya tidak perlu kode, saya hanya perlu matematika dasar di belakangnya."
David Richerby
@ DavidRicherby Saya mencoba menambahkan teks.
Xavier Combelle
Terima kasih. Dan saya melihat ada banyak kode di halaman ini, terlepas dari apa yang saya katakan!
David Richerby
0

Saya tahu cara mudah untuk melakukan konversi basis yang tidak memerlukan program komputer. Ini dengan mendefinisikan cara untuk mengkonversi dari basis mana saja ke basis 2 dan sebaliknya dan kemudian mencakup dari satu basis ke basis lain dengan terlebih dahulu mengkonversi dari basis pertama ke basis 2 kemudian mengubah dari basis 2 ke basis lainnya. 2 sangat mudah dikalikan atau dibagi dengan basis apa pun.

Untuk mengkonversi dari basis mana saja ke basis 2, yang harus Anda lakukan adalah mengenali bahwa untuk nomor berapa pun, jika Anda mengambil notasi basis 2 dan mulai dari 0 dan kemudian untuk setiap digit secara berurutan dari kiri ke kanan dua kali lipat jika angka itu nol dan dua kali lipat dari tambahkan 1 jika angka itu adalah 1, Anda mendapatkan nomor itu sendiri. Sekarang diberi nomor itu di pangkalan apa pun, Anda dapat membagi dengan 2 di pangkalan itu untuk mendapatkan hasil bagi dan sisanya. Jika sisanya adalah 1, digit biner terakhir adalah 1 dan jika sisanya adalah 0, digit biner terakhir adalah 0. Bagilah dengan 2 lagi. Jika sisanya adalah 1, digit terakhir kedua adalah 1 dan jika sisanya adalah 0, digit terakhir kedua adalah 0 dan seterusnya hingga Anda mendapatkan hasil bagi 0.

Untuk mengonversi dari basis 2 ke basis apa pun, yang harus Anda lakukan adalah di basis itu, mulai dari 0, lalu untuk setiap digit biner dari kiri ke kanan, gandakan di basis itu jika digit itu adalah 0 dan dobel kemudian tambahkan 1 di dalamnya mendasarkan jika digit itu adalah 1.

Timotius
sumber
2 is so easy to multiply or divide by in any base.Saya tidak melihat bahwa untuk pangkalan aneh yang lebih dari satu dari kekuatan dua (11 dan 13, untuk memulai).
greybeard
0

Anda dapat mengonversi dari basis n ke basis 10 tanpa konversi apa pun ke beberapa basis perantara.

Untuk mengkonversi dari basis n ke basis 9, misalnya, Anda mengambil algoritma untuk konversi ke basis 10, dan ganti "10" dengan "9". Sama untuk basis lainnya.

gnasher729
sumber