Keskustelu: Ohjelmointikysymykset: JavaScript: CSES tehtävä mahdoton javascriptillä?

Ihan mielenkiinnosta kysäisen tätä, että onko https://cses.fi/dt/task/314 tehtävä mahdollinen javascriptillä ilman bigInt -kirjastoa? Tehtävässä pitää käsitellä sen verran isoja lukuja, että javascript ei voi laskea niitä. Olen kyllä jakanut vastauksen tuolla modulo 10^9 + 7.

Javascript ei pysty laskemaan tuota test case kuutosta: 138367 --> Nan. Olisiko mahdollista, että cses:n testikoneen nodeen asennettaisiin bigInt?

On mahdollista. Tuo modulo on tehtävässä juuri sitä varten, että tehtävän voi laskea tavallisilla 32-bittisillä kokonaisluvuilla. Olennaista on tietää seuraavat jakojäännöksen ominaisuudet:

(a + b) mod m  =  ((a mod m) + (b mod m)) mod m
(a * b) mod m  =  ((a mod m) * (b mod m)) mod m

Eli jos koodi näyttää aiemmin tältä:

summa = 0;
foreach (tapaus) {
  summa += välitulos;
}
print(summa % 1000000007);

Niin koodin saa toimivaksi laskemalla jakojäännöksen joka kierroksella:

summa = 0;
foreach (tapaus) {
  // jos summa + välitulos on varmasti riittävän pieni:
  summa = (summa + välitulos) % 1000000007;
  // jos summa + välitulos saattaa ylittää muuttujan rajan:
  summa = (summa + välitulos % 1000000007) % 1000000007;
}
print(summa);

Tai kyseisessä tehtävässä:

tulos = 1;
for (var i = 0; i < n; ++i) {
  tulos = (tulos * 2) % 1000000007;
}
print(tulos);

Joskus harvoin täytyy laskea jakojäännöksiä myös muissa välivaiheissa, jolloin täytyy olla erityisen tarkkana, ettei jakojäännös ole väärässä välissä.

console.log(Math.pow(2, n) % 100000007)

Tein juurikin näin :D

Kyllä yksi tehtävä taitaa olla mahdoton (nodeJs). Spiraali -tehtävässä oikeat vastaukset ovat liian suuria.

Javascript tukee tarkkoja vastauksia 15 numeroon asti, jonka jälkeen se pyöristelee. Esimerkiksi test case 10:

Input:
449068555 514254328

Correct output:
264457513287291484

User output:
264457513287291500

Ongelma ilmenee Test Caseissa 6-10. Toivottavasti en ole taas väärässä ;D

Jos muu ei auta, niin voit käsitellä lukuja merkkijonoina ja toteuttaa itse tarvittavat operaatiot (esim. yhteen- ja kertolaskun). Ei ole siis mahdoton mutta kieltämättä voi olla hankalampi Node.js:llä.

Lisäks näyttäisi olevan erilaisia js-kirjastoja, joilla voi käsitellä isoja lukuja.

Puhuin juuri tuosta aloitusviestissäni (bigInt - kirjasto)

Kerkesin eilisiltana tehdä jo plus- ja kertolaskuille funktiot. Tänä iltana vielä vähennyslaskulle funktio ja sitten pitäisi toimia.

BigInt ei ole mikään kirjasto vaan js:n natiivi ominaisuus. Jos palvelimella oleva Node.js on liian vanha, niin tukea ei ole saatavilla. JS / Node ei edes ollut tuettujen alustojen listalla, joten ei järin suuri yllätys.

The Alchemist kirjoitti:

BigInt ei ole mikään kirjasto vaan js:n natiivi ominaisuus.

BigInt on kyllä nykyään tuettuna, muttei ole kauhean nopea (yli 2,5 minuuttia hitaampi laskemaan ja tulostamaan 1000000 numeron fibonaccin lukua kuin 8th) ja omaa joitain rajoituksia kuten esim. ettei Math objektia pysty käyttämään...

Muuten kyllä olen huomannut, että Node.js suorituskyky yleensä ottaen on erinomainen!

Sitä paitsi, pitäähän sitä ainakin kerran itse kirjoittaa oma Karatsuba toteutus isojen lukujen kertomista varten...

Testikoodi alla:

function fibo(n) {
  let numbits = Math.log2(n)
  let a = 0n
  let b = 1n
  for (let i = numbits; i >= 1; i--) {
    let d = a*(b*2n-a)
    let e = a*a+b*b
    if ((n >> i) & 1)  {
      a = e
      b = d+e
    } else {
      a = d
      b = e
    }
  }
  if (n & 1) {
    return a*a+b*b
  } else {
      return a*(2n*b-a)
  }
}

console.log(fibo(4784969).toString())