Bosan dengan lelucon JS yang konyol? Tulis perpustakaan Anda

Ada banyak hal dalam JavaScript yang mengundang pertanyaan "Apa ???". Terlepas dari kenyataan bahwa kebanyakan dari mereka memiliki penjelasan yang logis, jika Anda mendalami lebih dalam, mereka masih bisa mengejutkan. Tapi JavaScript jelas tidak pantas mendapatkan lelucon yang keterlaluan. Misalnya, terkadang kita melihat lelucon seperti ini:

Dalam hal ini, kritik sama sekali tidak layak. Mari kita cari tahu alasannya.

---

JavaScript, seperti bahasa pemrograman populer lainnya , merepresentasikan angka menggunakan satu standar. Tepatnya, ini adalah standar IEEE 754 untuk angka dalam format biner 64-bit. Mari kita coba untuk menguji lelucon yang sama dalam bahasa lain:



Bagaimana dengan Ruby? Dalam bahasa apa 0,1 + 0,2 tidak sama dengan 0,3?

$ irb
irb(main):001:0> 0.1 + 0.2 == 0.3
=> false
irb(main):002:0> 0.1 + 0.2
=> 0.30000000000000004
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Rubi! Bahasa yang bodoh.



Atau Clojure? Dalam bahasa apa 0,1 + 0,2 tidak sama dengan 0,3?

$ clj
Clojure 1.10.1
user=> (== (+ 0.1 0.2) 0.3)
false
user=> (+ 0.1 0.2)
0.30000000000000004

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Clojure! Bahasa yang bodoh.



Atau bagaimana dengan Haskell yang perkasa? Dalam bahasa apa 0,1 + 0,2 tidak sama dengan 0,3?

$ ghci
GHCi, version 8.10.1: https://www.haskell.org/ghc/  :? for help
Prelude> 0.1 + 0.2 == 0.3
False
Prelude> 0.1 + 0.2
0.30000000000000004

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Haskell! Ha ha ha. Betapa bodohnya bahasa ...



Anda mengerti. Masalahnya di sini bukanlah JavaScript. Ini adalah masalah besar dengan bilangan floating point biner. Tetapi saya tidak ingin membahas lebih dalam tentang IEEE 754 untuk saat ini, karena jika kita menginginkan angka yang tepat sewenang-wenang, JavaScript memungkinkannya. Sejak Oktober 2019, BigInt secara resmi menjadi bagian dari standar ECMAScript TC39 .

Mengapa repot-repot dengan ini?

Kami bertahan dengan IEEE 754 selama berabad-abad. Ini sepertinya tidak menjadi masalah di sebagian besar waktu. Benar. Ini hampir selalu tidak menjadi masalah. Namun terkadang hal itu tetap menjadi masalah. Dan di saat-saat seperti ini, ada baiknya memiliki pilihan.



Misalnya, awal tahun ini saya sedang mengerjakan perpustakaan grafik. Saya ingin menggambar grafik kandil dalam SVG. Dan SVG memiliki fitur rapi yang disebut transformasi . Anda dapat menerapkannya ke sekelompok item dan itu akan mengubah sistem koordinat untuk item tersebut. Jadi dengan sedikit hati-hati Anda dapat menyederhanakan pembuatan area bagan. Alih-alih menghitung koordinat grafik untuk setiap kandil, Anda menentukan satu transformasi. Dan kemudian tentukan setiap candle menggunakan nilai data mentah. Sangat rapi. Setidaknya dalam teori.



Tapi dalam tes properti saya mengalami masalah. Jika grafiknya kecil dan nilai datanya besar, saya akan mendapatkan kesalahan pembulatan. Dan ini seringkali normal. Tetapi pada grafik, beberapa piksel harus berbaris. Jika tidak, gambar terlihat salah. Jadi saya mulai belajar BigInt. Hasilnya adalah perpustakaan yang saya beri nama Ratio. Dan saya akan menunjukkan kepada Anda bagaimana itu ditulis.

Kelas pecahan

Masalah dengan bilangan floating point adalah representasi binernya. Komputer melakukan semua perhitungannya dalam bentuk biner. Dan untuk bilangan bulat biner ini baik-baik saja. Masalahnya muncul saat kita ingin merepresentasikan angka desimal. Misalnya, di negara-negara berbahasa Inggris seperti Australia, kami menulis desimal seperti ini:

$$

$$3.1415926$$

Bagian di sebelah kiri titik (...) adalah seluruh bagian, dan di sebelah kanan titik adalah bagian pecahan. Tetapi masalahnya adalah beberapa angka memiliki bagian pecahan yang tidak dapat dengan mudah dibagi menjadi dua. Jadi sulit untuk merepresentasikannya dalam biner. Tetapi masalah yang sama muncul di basis 10. Misalnya, pecahan 10/9. Anda dapat mencoba menulis sesuatu seperti ini:

$$

$$1.111111111111111111111111111111111111.11111111111111111111111111111111111$$

Namun, ini hanyalah perkiraan. Untuk merepresentasikan 10/9 secara akurat, unit harus tidak terbatas. Oleh karena itu, kita harus menggunakan notasi lain untuk merepresentasikan pengulangan. Contohnya begini:

$$

$$1.\dot{1}$$

Titik di atas unit ini menunjukkan bahwa unit melanjutkan. Tetapi kebanyakan bahasa pemrograman tidak memiliki poin ini.



Perhatikan bahwa 10/9 memiliki akurasi yang sempurna. Dan yang diperlukan untuk menjadi akurat hanyalah dua bagian informasi. Ini adalah pembilang dan penyebutnya . Dengan satu nilai BigInt, kita dapat mewakili bilangan bulat besar yang sewenang-wenang. Tetapi jika kita membuat sepasang bilangan bulat, kita dapat mewakili bilangan besar atau kecil secara sembarangan .



Dalam JavaScript, mungkin terlihat seperti ini:

// file: ratio.js
export default class Ratio {
  // We expect n and d to be BigInt values.
  constructor(n, d) {
    this.numerator = n;
    this.denominator = d;
  }
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Jadi kami melakukan bagian tersulit. "Menciptakan" cara untuk merepresentasikan angka dengan presisi hampir tak terbatas. (Kami masih dibatasi oleh memori perangkat kami.) Yang tersisa hanyalah menerapkan matematika. Jadi mari tambahkan fungsionalitas.

Persamaan

Hal pertama yang ingin Anda lakukan adalah membandingkan kedua pecahan. Untuk apa? Karena saya suka menulis tes dulu . Jika saya bisa membandingkan dua pecahan untuk persamaan, maka tes menulis jauh lebih mudah.



Dalam kasus sederhana, menulis metode kesetaraan cukup mudah:

// file: ratio.js
export default class Ratio {
  constructor(n, d) {
    this.numerator = n;
    this.denominator = d;
  }

  equals(other) {
    return (
      this.numerator === other.numerator &&
      this.denominator === other.denominator
    );
  }
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Itu bagus. Tapi alangkah baiknya jika perpustakaan kita bisa mengatakan 1/2 adalah 2/4. Untuk melakukannya, Anda perlu menyederhanakan pecahan. Artinya, sebelum memeriksa persamaan, kita ingin mengurangi pembilang dan penyebut dari kedua pecahan menjadi angka sekecil mungkin. Jadi bagaimana kita melakukan ini?



Pendekatan naif adalah menjalankan semua bilangan dari 1 hingga min (n, d) (di mana nn dan dd adalah pembilang dan penyebutnya masing-masing). Dan inilah yang saya coba di awal. Kode tersebut terlihat seperti ini:

function simplify(numerator, denominator) {
    const maxfac = Math.min(numerator, denominator);
    for (let i=2; i<=maxfac; i++) {
      if ((numerator % i === 0) && (denominator % i === 0)) {
        return simplify(numerator / i, denominator / i);
      }
    }
    return Ratio(numerator, denominator);
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Dan, seperti yang Anda duga, ini sangat lambat. Tes saya memakan waktu lama. Jadi kita membutuhkan pendekatan yang lebih efisien. Untungnya, seorang ahli matematika Yunani menemukannya beberapa milenium yang lalu. Solusinya adalah dengan menerapkan algoritma Euclid. Ini adalah cara untuk mencari pembagi persekutuan terbesar dari dua bilangan bulat.



Versi rekursif dari algoritma Euclid cantik dan elegan:

function gcd(a, b) {
    return (b === 0) ? a : gcd(b, a % b);
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Memoisasi dapat diterapkan, yang membuat algoritme cukup menarik. Namun sayang, kami belum memiliki rekursi ekor di V8 atau SpiderMonkey . (Setidaknya tidak pada saat penulisan ini.) Ini berarti bahwa jika kita menjalankannya dengan bilangan bulat yang cukup besar, kita mendapatkan stack overflow. Bilangan bulat besar seperti titik awal.



Jadi mari gunakan versi iteratif sebagai gantinya:

// file: ratio.js
function gcd(a, b) {
    let t;
    while (b !== 0) {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Tidak begitu elegan, tapi berhasil. Dan dengan kode ini, kita dapat menulis fungsi untuk menyederhanakan pecahan. Saat kita melakukan ini, kita akan membuat perubahan kecil sehingga penyebutnya selalu positif (yaitu, untuk bilangan negatif, hanya pembilang yang mengubah tandanya).

// file: ratio.js

function sign(x) {
  return x === BigInt(0) ? BigInt(0)
       : x > BigInt(0)   ? BigInt(1) 
       /* otherwise */   : BigInt(-1);
}

function abs(x) {
  return x < BigInt(0) ? x * BigInt(-1) : x;
}

function simplify(numerator, denominator) {
  const sgn = sign(numerator) * sign(denominator);
  const n = abs(numerator);
  const d = abs(denominator);
  const f = gcd(n, d);
  return new Ratio((sgn * n) / f, d / f);
}

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Dan sekarang kita bisa menulis metode kesetaraan kita:

// file: ratio.js -- inside the class declaration
  equals(other) {
    const a = simplify(this);
    const b = simplify(other);
    return (
      a.numerator === b.numerator &&
      a.denominator === b.denominator
    );
  }

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Sekarang Anda dapat membandingkan dua pecahan untuk persamaan. Mungkin kedengarannya tidak banyak, tetapi itu berarti kita dapat menulis pengujian unit dan memastikan perpustakaan kita berfungsi seperti yang diharapkan.

Konversi ke jenis lain

Saya tidak akan membuat Anda bosan dengan menuliskan semua unit test di perpustakaan saya. Tetapi alangkah baiknya untuk mengubah pecahan ke format lain. Misalnya, kami mungkin ingin mewakilinya sebagai string dalam pesan debug. Atau mungkin kita ingin mengubahnya menjadi angka. Jadi mari kita timpa metode .toString () dan .toValue () untuk kelas kita.



Metode .toString () adalah yang termudah, jadi mari kita mulai dengan itu.

// file: ratio.js -- inside the class declaration
  toString() {
    return `${this.numerator}/${this.denominator}`;
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Cukup sederhana. Tetapi bagaimana dengan mengubah kembali menjadi angka? Salah satu cara untuk melakukannya adalah dengan membagi pembilang dengan penyebut:

// file: ratio.js -- inside the class declaration
  toValue() {
    return  Number(this.numerator) / Number(this.denominator);
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Ini sering berhasil. Tetapi kami mungkin ingin sedikit mengubah kodenya. Inti dari perpustakaan kami adalah kami menggunakan bilangan bulat besar untuk mendapatkan ketepatan yang kami butuhkan. Dan terkadang bilangan bulat ini terlalu besar untuk diubah kembali menjadi Angka. Tapi kami ingin mendapatkan Nomor sedekat mungkin dengan kebenaran, jika memungkinkan. Jadi kami melakukan beberapa aritmatika saat mengubah BigInt menjadi Number:

// file: ratio.js -- inside the class declaration
  toValue() {
    const intPart = this.numerator / this.denominator;
    return (
      Number(this.numerator - intPart * this.denominator) /
        Number(this.denominator) + Number(intPart)
    );
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Dengan mengekstrak bagian integer, kami mengurangi ukuran nilai BigInt sebelum mengubahnya menjadi Number. Ada cara lain untuk melakukan ini yang memiliki masalah jangkauan yang lebih kecil. Mereka umumnya lebih keras dan lebih lambat. Jika Anda tertarik, saya sarankan Anda melihat lebih dalam. Namun dalam artikel ini, pendekatan sederhana mencakup cukup banyak kasus agar bermanfaat.

Perkalian dan pembagian

Mari kita lakukan sesuatu dengan angka-angka itu. Bagaimana dengan perkalian dan pembagian? Mudah untuk pecahan. Kalikan pembilang dengan pembilang dan penyebut dengan penyebut.

// file: ratio.js -- inside the class declaration
  times(x) {
    return simplify(
      x.numerator * this.numerator,
      x.denominator * this.denominator
    );
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Pembagian mirip dengan kode di atas. Balik pecahan kedua, lalu kalikan.

// file: ratio.js -- inside the class declaration
  divideBy(x) {
    return simplify(
      this.numerator * x.denominator,
      this.denominator * x.numerator
    );
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Penambahan dan pengurangan

Kami sekarang memiliki perkalian dan pembagian. Logikanya, hal berikutnya yang harus ditulis adalah penjumlahan dan pengurangan. Ini sedikit lebih rumit daripada perkalian dan pembagian. Tapi jangan terlalu banyak.

Untuk menjumlahkan dua pecahan, pertama-tama Anda harus memasukkannya ke penyebut yang sama, lalu menambahkan pembilangnya. Dalam kode, mungkin terlihat seperti ini:

// file: ratio.js -- inside the class declaration
  add(x) {
    return simplify(
      this.numerator * x.denominator + x.numerator * this.denominator,
      this.denominator * x.denominator
    );
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Semuanya dikalikan dengan penyebutnya. Dan kami menggunakan simplify () untuk menjaga pecahan sekecil mungkin dalam hal angka pembilang dan penyebut.

Pengurangan mirip dengan penjumlahan. Kami memanipulasi dua pecahan sehingga penyebut yang sama berbaris seperti sebelumnya. Kemudian kami tidak menambah, tetapi mengurangi.

// file: ratio.js -- inside the class declaration
  subtract(x) {
    return simplify(
      this.numerator * x.denominator - x.numerator * this.denominator,
      this.denominator * x.denominator
    );
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Jadi, kami memiliki operator dasar. Anda dapat menambah, mengurangi, mengalikan, dan membagi. Tetapi kami masih membutuhkan beberapa metode lain. Secara khusus, angka memiliki sifat penting: kita dapat membandingkannya satu sama lain.

Perbandingan

Kami telah membahas .equals (). Tapi kita membutuhkan lebih dari sekedar kesetaraan. Kami juga ingin menentukan rasio yang lebih besar-lebih sedikit. Oleh karena itu, kita akan membuat metode .lte () yang akan memberi tahu kita apakah satu pecahan kurang dari atau sama dengan pecahan lainnya. Seperti halnya .equals (), tidak jelas mana yang lebih kecil. Untuk membandingkannya, kita perlu mengonversi keduanya menjadi penyebut yang sama, lalu membandingkan pembilangnya. Dengan sedikit penyederhanaan yang berlebihan, akan terlihat seperti ini:

// file: ratio.js -- inside the class declaration
  lte(other) {
    const { numerator: thisN, denominator: thisD } = simplify(
      this.numerator,
      this.denominator
    );
    const { numerator: otherN, denominator: otherD } = simplify(
      other.numerator,
      other.denominator
    );
    return thisN * otherD <= otherN * thisD;
  }

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Setelah kita memiliki .lte () dan .equals (), kita dapat mencetak perbandingan lainnya. Anda dapat memilih operator perbandingan apa saja. Tetapi jika kita memiliki persamaan () dan>, <, ≥ atau ≤, maka kita dapat menyimpulkan sisanya menggunakan logika boolean. Dalam kasus ini, kami memilih lte () karena standar FantasyLand menggunakannya . Operator lain mungkin terlihat seperti ini:

// file: ratio.js -- inside the class declaration
  lt(other) {
    return this.lte(other) && !this.equals(other);
  }

  gt(other) {
    return !this.lte(other);
  }

  gte(other) {
    return this.gt(other) || this.equals(other);
  }

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Pembulatan

Sekarang kita bisa membandingkan pecahan. Dan kita juga bisa mengalikan dan membagi, menambah dan mengurangi. Tetapi jika kita ingin melakukan lebih banyak kesenangan dengan perpustakaan kita, kita membutuhkan lebih banyak alat. Objek kenyamanan JavaScript Math berisi metode .floor () dan .ceil ().

Mari kita mulai dengan .floor (). Lantai mengambil nilai dan membulatkannya ke bawah. Dengan bilangan positif, ini berarti kita hanya menyimpan sebagian dan membuang sisanya. Tetapi untuk bilangan negatif kita membulatkannya dari nol, jadi bilangan negatif perlu lebih diperhatikan.

// file: ratio.js -- inside the class declaration
  floor() {
    const one = new Ratio(BigInt(1), BigInt(0));
    const trunc = simplify(this.numerator / this.denominator, BigInt(1));
    if (this.gte(one) || trunc.equals(this)) {
      return trunc;
    }
    return trunc.minus(one);
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Sekarang Anda dapat menggunakan kode di atas untuk menghitung nilai yang dibulatkan.

// file: ratio.js -- inside the class declaration
  ceil() {
    const one = new Ratio(BigInt(1), BigInt(0));
    return this.equals(this.floor()) ? this : this.floor().add(one);
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Kami sekarang memiliki sebagian besar dari apa yang dibutuhkan untuk banyak operasi matematika. Dan dengan .toValue () kita dapat dengan mudah mengubah kalkulasi kembali ke angka desimal. Tetapi bagaimana jika kita ingin mengubah bilangan floating point menjadi pecahan?

Angka menjadi pecahan

Mengubah angka menjadi pecahan lebih sulit daripada yang terlihat pada pandangan pertama. Dan ada banyak cara berbeda untuk melakukan transformasi ini. Implementasi saya bukan yang paling akurat, tapi cukup bagus. Untuk membuatnya berfungsi, pertama-tama kita mengonversi bilangan tersebut menjadi string, yang, seperti yang kita ketahui, akan menggunakan format urutan. Untuk melakukan ini, JavaScript memberi kita metode .toExponential (). Metode ini mengembalikan angka dalam notasi eksponensial. Berikut beberapa contoh untuk membantu Anda memahami gagasan tersebut:

let x = 12.345;
console.log(x.toExponential(5));
// ⦘ '1.23450e+1''

x = 0.000000000042;
console.log(x.toExponential(3));
// ⦘ '4.200e-11'

x = 123456789;
console.log(x.toExponential(4));
// ⦘ '1.2346e+8'

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Kode tersebut bekerja dengan merepresentasikan angka sebagai nilai desimal yang dinormalisasi dan pengganda. Bit desimal yang dinormalisasi disebut mantissa, dan faktornya disebut eksponen. Di sini "dinormalisasi" berarti nilai absolut mantisa selalu kurang dari 10. Dan eksponennya selalu sekarang 10. Kami menunjukkan awal faktor dengan huruf 'e' (kependekan dari 'eksponen').



Keuntungan dari notasi ini adalah konsisten. Selalu ada satu digit di kiri koma desimal. Dan .toExponential () memungkinkan kita menentukan berapa banyak digit signifikan yang kita inginkan. Kemudian muncul 'e' dan eksponen selalu berupa bilangan bulat. Karena nilainya berurutan, kita dapat menggunakan regex nakal untuk menguraikannya.



Prosesnya berjalan seperti ini. Seperti disebutkan, .toExponential () mengambil parameter untuk menentukan jumlah digit signifikan. Kami membutuhkan nomor sebanyak mungkin. Jadi, kami menetapkan presisi ke 100 (yang memungkinkan sebagian besar mesin JavaScript). Untuk contoh ini, bagaimanapun, kita akan tetap dengan presisi 10. Sekarang bayangkan kita memiliki angka 0,987654321e0. Kami ingin memindahkan koma desimal 10 digit ke kanan. Hasilnya adalah 9876543210. Kemudian bagi dengan 10 ^ 10 untuk mendapatkan 9876543210/100000000. Ini, pada gilirannya, disederhanakan menjadi 987654321/100000000.



Tapi kita harus memperhatikan eksibitor ini. Jika kita memiliki bilangan seperti 0.987654321e9, maka kita akan tetap menggeser koma desimal 10 digit ke kanan. Tapi kita membaginya dengan sepuluh, dengan pangkat 10-9 = 1.

$$

$$0.987654321×10^9 = 9876543210/ 10^1=$$

$$

$$987654321/1$$

Agar tetap seperti itu, kami telah menetapkan beberapa fungsi helper:

// Transform a ‘+’ or ‘-‘ character to +1 or -1
function pm(c) {
  return parseFloat(c + "1");
}

// Create a new bigint of 10^n. This turns out to be a bit
// faster than multiplying.
function exp10(n) {
  return BigInt(`1${[...new Array(n)].map(() => 0).join("")}`);
}
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Dengan bantuan mereka, kita bisa menyatukan seluruh fungsi fromNumber ().

// file: ratio.js -- inside the class declaration
  static fromNumber(x) {
    const expParse = /(-?\d)\.(\d+)e([-+])(\d+)/;
    const [, n, decimals, sgn, pow] =
      x.toExponential(PRECISION).match(expParse) || [];
    const exp = PRECISION - pm(sgn) * +pow;
    return exp < 0
      ? simplify(BigInt(`${n}${decimals}`) * exp10(-1 * exp), BigInt(1))
      : simplify(BigInt(`${n}${decimals}`), exp10(exp));
  }

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Sebagian besar fungsi dasar tercakup. Kita bisa beralih dari angka ke pecahan dan kembali lagi. Tetapi untuk aplikasi khusus saya, saya membutuhkan lebih banyak. Secara khusus, perlu untuk menemukan eksponensiasi dan logaritma.

Eksponensial

Eksponensial adalah ketika sebuah angka dikalikan berkali-kali dengan sendirinya. Misalnya, 2 ^ 3 = 2 × 2 × 2 = 8. Untuk kasus sederhana di mana derajatnya adalah bilangan bulat, ada operator BigInt: ** bawaan. Jadi jika kita meningkatkan sebagian kecil dari kekuasaan, itu pilihan yang bagus. Beginilah cara suatu pecahan dipangkatkan:

$$

$$\left(\frac{x}{y}\right)^{n} = \frac{x^n}{y^n}$$

Oleh karena itu, bagian pertama dari metode eksponen kami mungkin terlihat seperti ini:

// file: ratio.js -- inside the class declaration
  pow(exponent) {
    if (exponent.denominator === BigInt(1)) {
        return simplify(
            this.numerator ** exponent.numerator,
            this.denominator ** exponent.numerator
        );
    }
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Bekerja dengan baik. Yah ... kebanyakan bagus. Sekarang segalanya menjadi lebih rumit. Di luar batasan agunan dan matematika, kita harus membuat beberapa trade-off. Kami mungkin harus mengorbankan keakuratan untuk mendapatkan tanggapan dalam jangka waktu yang wajar.



Eksponensial dengan mudah menghasilkan angka besar. Dan ketika angkanya menjadi besar, segalanya melambat. Saat saya menulis artikel ini, saya juga menulis perhitungan yang tidak selesai selama beberapa hari. Jadi Anda perlu berhati-hati. Tapi tidak apa-apa. Semuanya datang untuk BigInt.



Tapi ada masalah lain. Bagaimana jika penyebut derajatnya bukan satu? Misalnya, bagaimana jika kita ingin menghitung 8 ^ (2/3)?



Untungnya, kita dapat membagi masalah ini menjadi dua masalah yang lebih kecil. Kami ingin mengurangi satu fraksi menjadi kekuatan fraksi lainnya. Misalnya, kita dapat mengatribusikan x / y ke a / b. Hukum eksponen menyatakan bahwa yang berikut ini setara:

$$

$$\left(\frac{x}{y}\right)^\frac{a}{b} = \left(\left(\frac{x}{y}\right)^\frac{1}{b}\right)^a = \left(\frac{x^\frac{1}{b}}{y^\frac{1}{b}}\right)^a$$

Kita sudah tahu bagaimana mengubah satu BigInt menjadi kekuatan BigInt lainnya. Tapi bagaimana dengan derajat pecahan? Nah, ada persamaan lainnya:

$$

$$x^\frac{1}{n} = \sqrt[n]{x}$$

Artinya, mengurangi xx ke pangkat 1n1n sama dengan mencari akar ke-n dari xx. Ini berarti bahwa jika kita menemukan cara untuk menghitung root ke-n BigInt, maka kita dapat menghitung derajat apa pun.



Dengan penelusuran web yang matang, menemukan algoritme untuk memperkirakan akar ke-n seharusnya tidak membutuhkan waktu lama. Metode yang paling umum adalah metode Newton . Ini bekerja dari evaluasi, rr. Kemudian dilakukan perhitungan untuk mendapatkan estimasi terbaik:

$$

$$\begin{align} r &\approx x^{\frac{1}{n}} \\ r^{\prime} &= \frac{1}{n}\left((n-1)r + \left(\frac{x}{r^{n-1}}\right)\right) \end{align}$$

Kami terus mengulangi perhitungan ini hingga mencapai akurasi yang diinginkan. Sayangnya, ada beberapa akar yang tidak dapat direpresentasikan sebagai pecahan hingga. Dengan kata lain, kita membutuhkan nilai BigInt yang sangat panjang untuk mendapatkan presisi yang sempurna. Dalam praktiknya, ini berarti kita harus memilih batasan iterasi yang sewenang-wenang.



Kami akan kembali ke titik ini. Untuk saat ini, mari kita cari tahu cara menghitung akar n yang cukup akurat. Karena perkiraan rr adalah pecahan, kita dapat menuliskannya sebagai:

$$

$$r = \frac{a}{b}.$$

Dan ini memungkinkan kami untuk menulis ulang perhitungan seperti ini:

$$

$$\frac{a^{\prime}}{b^{\prime}} = \frac{(n - 1)a^{n} + x b^{n}}{n b a^{n - 1}}$$

Sekarang semuanya dalam hal komputasi integer, cocok untuk digunakan dengan BigInt. Jangan ragu untuk memasukkan abab ke dalam persamaan untuk r′r ′ di atas dan periksa temuan saya. Dalam JavaScript, tampilannya seperti ini:

const estimate = [...new Array(NUM_ITERATIONS)].reduce(r => {
  return simplify(
    (n - BigInt(1)) * r.numerator ** n + x * r.denominator ** n,
    n * r.denominator * r.numerator ** (n - BigInt(1))
  );
}, INITIAL_ESTIMATE);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Kami hanya mengulangi perhitungan ini sampai kami mencapai presisi yang sesuai untuk estimasi akar ke-n kami. Masalahnya adalah kita perlu menghasilkan nilai yang sesuai untuk konstanta kita. Yaitu, NUM_ITERATIONS dan INITIAL_ESTIMATE.

Banyak algoritme dimulai dengan INITIAL_ESTIMATE satu. Ini adalah pilihan yang cerdas. Seringkali kita tidak memiliki cara yang baik untuk menebak apa kemungkinan akar n itu. Tapi mari kita tulis "halangan". Mari kita asumsikan (untuk saat ini) bahwa pembilang dan penyebut kita berada dalam kisaran Angka. Kita kemudian bisa menggunakan Math.pow () untuk mendapatkan skor awal. Ini mungkin terlihat seperti ini:

// Get an initial estimate using floating point math
// Recall that x is a bigint value and n is the desired root.
const initialEstimate = Ratio.fromNumber(
    Math.pow(Number(x), 1 / Number(n))
);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Jadi kami memiliki nilai untuk penilaian awal kami. Bagaimana dengan NUM_ITERATION? Nah, dalam praktiknya, yang saya lakukan adalah mulai dengan asumsi 10. Lalu saya melakukan tes properti. Saya terus menambah jumlahnya hingga kalkulasi berada dalam kerangka waktu yang wajar. Dan angka yang akhirnya berhasil ... 1. Satu iterasi. Ini sedikit membuat saya sedih, tetapi kami sedikit lebih akurat dibandingkan dengan perhitungan floating point. Dalam praktiknya, Anda dapat menambah angka ini jika Anda tidak menghitung banyak pangkat pecahan.



Untuk mempermudah, kami akan mengekstrak kalkulasi dari akar ke-n menjadi fungsi terpisah. Menggabungkan semuanya, kodenya mungkin terlihat seperti ini:

// file: ratio.js -- inside the class declaration
  static nthRoot(x, n) {
    // Handle special cases
    if (x === BigInt(1)) return new Ratio(BigInt(1), BigInt(1));
    if (x === BigInt(0)) return new Ratio(BigInt(0), BigInt(1));
    if (x < 0) return new Ratio(BigInt(1), BigInt(0)); // Infinity

    // Get an initial estimate using floating point math
    const initialEstimate = Ratio.fromNumber(
      Math.pow(Number(x), 1 / Number(n))
    );

    const NUM_ITERATIONS = 1;
    return [...new Array(NUM_ITERATIONS)].reduce((r) => {
      return simplify(
        n -
          BigInt(1) * (r.numerator ** n) +
          x * (r.denominator ** n),
        n * r.denominator * r.numerator ** (n - BigInt(1))
      );
    }, initialEstimate);
  }

  pow(n) {
    const { numerator: nNumerator, denominator: nDenominator } = n.simplify();
    const { numerator, denominator } = this.simplify();
    if (nNumerator < 0) return this.invert().pow(n.abs());
    if (nNumerator === BigInt(0)) return Ratio.one;
    if (nDenominator === BigInt(1)) {
      return new Ratio(numerator ** nNumerator, denominator ** nNumerator);
    }
    if (numerator < 0 && nDenominator !== BigInt(1)) {
      return Ratio.infinity;
    }

    const { numerator: newN, denominator: newD } = Ratio.nthRoot(
      numerator,
      nDenominator
    ).divideBy(Ratio.nthRoot(denominator, nDenominator));
    return new Ratio(newN ** nNumerator, newD ** nNumerator);
  }

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Tidak sempurna dan lambat. Tetapi tugas itu sebagian besar bisa dilakukan. Pertanyaannya tetap bagaimana cara mendapatkan perkiraan jika kita memiliki bilangan bulat yang lebih besar dari Number.MAX_VALUE. Namun, saya akan meninggalkan ini sebagai latihan untuk pembaca; artikel ini sudah terlalu panjang.

Logaritma

Harus saya akui, logaritma membingungkan saya selama beberapa minggu. Untuk pengembangan saya, saya perlu menghitung logaritma basis 10. Jadi saya mencari algoritma untuk menghitung logaritma. Dan ada banyak dari mereka. Tetapi saya tidak dapat menemukan satu pun yang bekerja cukup baik untuk dimasukkan ke dalam perpustakaan matematika.



Mengapa sangat sulit? Tujuan saya adalah menghitung logaritma agar lebih presisi daripada angka floating point. Kalau tidak, mengapa semua ini? Fungsi logaritma floating-point, Math.log10 (), cepat dan built-in. Jadi, saya melihat algoritme yang menyediakan cara untuk menghitung logaritma secara berulang. Dan mereka bekerja. Tapi mereka lambat dalam mendapatkan presisi yang lebih tinggi dari floating point. Bukan hanya sedikit lebih lambat. Jauh lebih lambat.



Saat kita melakukan iterasi, pecahan yang kita buat menjadi lebih akurat. Tapi akurasi ini ada harganya. Nilai BigInt dalam pecahan semakin besar dan besar. Dan ketika mereka semakin besar, mereka mulai membutuhkan waktu lama untuk berkembang biak. Suatu saat, saya meninggalkan perhitungan selama tiga hari. Tetapi ketika kalkulasi sedang berlangsung, saya teringat sesuatu.



Saya ingat bahwa saya memerlukan metode log10 () agar dapat menghitung nilai skala yang bagus untuk grafik. Dan untuk kalkulasi ini, setiap kali saya memanggil .log10 (), saya langsung memanggil .floor (). Ini berarti saya hanya ingin bagian integer dari logaritma. Menghitung logaritma hingga 100 tempat desimal hanya membuang-buang waktu dan tenaga.



Selain itu, ada cara mudah untuk menghitung seluruh bagian dari logaritma basis 10. Yang kita butuhkan hanyalah menghitung angkanya. Upaya yang naif mungkin terlihat seperti ini:

// file: ratio.js -- inside the class declaration
  floorLog10() {
    return simplify(BigInt((this.numerator / this.denominator).toString().length - 1), BigInt(1));
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Sayangnya, ini tidak berfungsi untuk nilai yang kurang dari 1. Namun demikian, kita dapat menggunakan beberapa hukum logaritmik untuk bekerja dengan nilai seperti itu.

$$

$$\begin{align} \log_{10}\left(\frac{a}{b}\right) &= \log_{10}(a) - \log_{10}(b) \\ \log_{10}\left(\frac{1}{x}\right) &= \log_{10}(1) - \log_{10}(x) \\ &= -\log_{10}(x) \end{align}$$

Karena itu:

$$

$$\log_{10}\left(\frac{b}{a}\right) = -\log_{10}\left(\frac{a}{b}\right)$$

Menggabungkan semuanya, kita mendapatkan metode floorLog10 () yang lebih kuat:

// file: ratio.js -- inside the class declaration

  invert() {
    return simplify(this.denominator, this.numerator);
  }

  floorLog10() {
    if (this.equals(simplify(BigInt(0), BigInt(1)))) {
      return new Ratio(BigInt(-1), BigInt(0));
    }
    return this.numerator >= this.denominator
      ? simplify((this.numerator / this.denominator).toString().length - 1, 1)
      : simplify(BigInt(-1), BigInt(1)).subtract(this.invert().floorLog10());
  }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Lagi. Mengapa menderita?

Saat ini, perpustakaan memiliki semua fungsi yang diperlukan untuk aplikasi saya, untuk bekerja dengan grafik. Tapi mungkin masih menarik, kenapa semua ini repot? Sudah ada beberapa pustaka presisi arbitrer. Mengapa tidak menggunakan salah satunya dan menyelesaikannya?



Sejujurnya, saya akan menggunakan perpustakaan yang ada dalam banyak kasus. Apalagi jika saya sedang terburu-buru. Tidak ada gunanya melakukan semua ini jika seseorang telah melakukan pekerjaan unggul.



Kata kuncinya di sini adalah superior. Dan di sinilah motif saya untuk ingin menulis perpustakaan saya sendiri ikut bermain. Metode floorLog10 () di atas adalah contoh sempurna. Ini memberikan perhitungan yang tepat yang saya butuhkan untuk apa yang ingin saya lakukan. Ia melakukannya secara efisien, dalam sekitar enam baris kode.



Jika saya menggunakan perpustakaan orang lain, saya akan mengalami salah satu dari dua hal berikut:

1. Pengembang tidak mengimplementasikan log10 () atau metode logaritmik lainnya.

atau

1. Pengembang telah mengimplementasikan metode log10 () (atau yang setara).

Dalam skenario pertama, saya masih harus menulis floorLog10 (). Dalam situasi kedua, saya mungkin akan menggunakan metode logaritmik mereka. Dan kode saya akan menjadi lebih lambat dan lebih kompleks dari yang seharusnya.



Menulis perpustakaan saya sendiri memungkinkan saya menyesuaikannya dengan aplikasi saya. Tentu saja orang lain mungkin menganggap kode ini berguna, tetapi saya tidak bertanggung jawab atas kebutuhan mereka. Sehingga aplikasi saya tidak harus membawa kode kompleks yang tidak pernah digunakannya.



Selain itu, saya belajar banyak dengan membuat perpustakaan sendiri. Sekarang saya memahami batasan BigInt jauh lebih baik dalam praktiknya daripada sebelumnya. Saya tahu saya dapat menyetel kinerja metode root ke-n. Saya dapat menyesuaikannya tergantung pada seberapa banyak komputasi yang saya lakukan dan seberapa presisi yang saya butuhkan.



Terkadang ada baiknya menulis perpustakaan tujuan umum Anda sendiri. Bahkan jika Anda tidak berencana untuk membuka kode tersebut. Bahkan jika tidak ada orang lain yang menggunakannya. Anda bisa belajar banyak dan juga bisa mendatangkan kegembiraan.



Jika Anda ingin tahu lebih banyak tentang masalah floating point, lihat 0.30000000000000004.com . Dan jika Anda ingin melihat seluruh perpustakaan dan melakukan beberapa perhitungan, Anda dapat memeriksa kotak pasir ini dengan kodenya .

• Kursus JavaScript
• Pelatihan profesi Ilmu Data
• Pelatihan Analis Data