Sayılar değişkenler için çok büyük

1 ^ 1 + 2 ^ 2 + 3 ^ 3 .. + 1000 ^ 1000'in son on basamağını bulacağım. Bunu saf mantıkla bulmanın bir yolu var mı? Bence o kadar büyük bir sayı saklayamazsın.

Bu soru bir matematik yarışmasından geliyor ama bunu Java ile yapmaya çalışmayı düşündüm.

1
@demostene: "Bu soru matematik yarışmasından geliyor, ama bunu Java'da yapmaya çalışıyorum."
katma yazar BoltClock, kaynak
BigIntegers'a bir bak, bu sayıları saklayacak kadar büyükler.
katma yazar Kevin Cruijssen, kaynak
Tahminen XOR işlecini, üsteleme karşı durmak için kullanıyorsunuzdur. Değilse cevap 0'dır.
katma yazar Bathsheba, kaynak
math.stackexchange.com adresini deneyin
katma yazar panagdu, kaynak
@BoltClock Önce algoritmayı biliyorsanız, java'da yapmak daha kolaydır;)
katma yazar panagdu, kaynak
En az önemli 10 hane? Bunun için sadece 10 ^ 10 numaraya ihtiyacınız olacak. Bir uzun olur; int değil.
katma yazar Joop Eggen, kaynak
Sayıların o kadar büyük olmasına izin vermene gerek yok. Yüksek rakamların (sola doğru kapalı) asla alt rakamları (istediğinizleri) etkilemediğini gözlemleyin.
katma yazar harold, kaynak
"70F1" 'de [2] (F) rakamının 240 değerine sahip olduğunu söyleyebilirsiniz, çünkü sağdan sola 2. olur, bu nedenle rakamın gerçek değeri n * sizeOfBase ^ pos Rakamın birim değeri, bu durumda sizeOfBase 10 ve sağa sola 0 indeksli konumunu yerleştirin. Son sayı, her basamağın göreceli değerlerinin toplamıdır. Şimdi, bu mantıkları alın ve sizeOfBase = Integer.MAX_VALUE yapın, rakamları temsil etmek için bir sayı dizisi kullanın ve işte. java.math.BigInteger 'ı muhtemelen sakar bir şekilde, ama yine de yeniden icat ettiniz.
katma yazar Felype, kaynak
Evet, bunun mantığını bulmak istiyorum. Bu bir matematik yarışması sorusuydu, belli ki çocuklar bunu kalemle ve kağıtla yapmalı (bazı mantıklar)
katma yazar Jason, kaynak
Aslında henüz hiçbir şey denemedim.
katma yazar Jason, kaynak

7 cevap

O kadar büyük bir sayı saklamanıza gerek yok, sadece son on haneye ihtiyacınız var. Bunu uzun süre saklayabilirsiniz.

Büyük güçleri hesaplamak için etkili bir yol çarpmak ve kareler örn. 19 ^ 19 = 19 * 19 ^ 2 * 19 ^ 16 = 19 * 19 ^ 2 * 19 ^ 2 ^ 2 ^ 2 ^ 2. 10 ^ 10'dan büyük bir değeriniz olduğunda, son 10 haneyi kısaltabilirsiniz.

BTW, 1000 ^ 1000'in son on basamağı 0000000000'dir ve bunu toplamınıza eklediğinizde sıfır eklemekle aynıdır;


Düzenleme: BigInteger kullanmak zorunda olmamanıza rağmen, yazması daha kolaydır.

BigInteger tenDigits = BigInteger.valueOf(10).pow(10);
BigInteger sum = BigInteger.ZERO;
for (int i= 1; i <= 1000; i++) {
    BigInteger bi = BigInteger.valueOf(i);
    sum = sum.add(bi.modPow(bi, tenDigits));
}
sum = sum.mod(tenDigits);

modPow is more efficient than pow with mod seperately as it doesn't have to calculate very large numbers, only the result of the mod.

4
katma
@Misafir ilginç, ancak bunun cevabımla ne kadar ilgili olduğunu anlamıyorum.
katma yazar Peter Lawrey, kaynak
btw 999 ^ 999 son haneler değil ... 0000000
katma yazar Alex Salauyou, kaynak
BTW, 1 ^ 1 + 2 ^ 2 + 3 ^ 3 .. + 1000 ^ 1000'in son on hanesi 0000000000 değildir. Çünkü 1 ^ 1 + 2 ^ 2 + 3 ^ 3 .. + 1000 ^ 1000 değeri yalnızca 9 basamaklı bir sayı olan 333833500
katma yazar The Guest, kaynak
@PeterLawrey Bir hata yaptım. Sorunun ilk n doğal sayının karelerinin toplamı hakkında olduğunu düşündüm. Yorumum geçerli değil. Gösterdiğin için teşekkürler.
katma yazar The Guest, kaynak

BigIntegers'ı kullanabilirsin ...

public static void main(String[] args) {
    BigInteger acc = BigInteger.ZERO;

    for (int k = 1; k <= 1000; k++) {
        BigInteger pow = BigInteger.valueOf(k).pow(k);
        acc = acc.add(pow);
    }

    System.out.println(acc);
}
2
katma
Yukarıda belirtildiği gibi, eğer bu bir matematik bulmacası içinse, cevabı yazmak sadece aradıkları şeyin ne olduğunu sanmıyorum ...
katma yazar BretC, kaynak
Başka bir not - "k" bir milyona kadar çıkacak olsaydı, bunun çalışması uzun zaman alacak!
katma yazar BretC, kaynak

Sorunun Proje Euler'den geldiğine inanıyorum, bu sadece bir matematik sorunu değil; bazı hesaplamalar da gerektirmelidir. Bir bilgisayarın yapabileceği hesaplamaları çoğaltmaktan başka, kalem ve kağıtla nasıl çözülebileceğini bilmiyorum. Tamamen matematiksel bir çözüm yolunda pek bir şey göremiyorum. Ancak matematik, kodu optimize etmemize yardımcı olabilir.

Bir ^ n yükseltmek için n'nin ikili genişlemesini bulun:

n = n_k x 2^k + n_(k-1) x 2^(k-1) + ... + n_0 x 2^0 

burada n_i = 0 veya 1 , sağda sıfırıncı rakamı bulunan n ikili rakamlarıdır. Sonra

a^n = a^(n_k x 2^k) x a^(n_(k-1) x 2^(k-1)) x ... x a^(n_0 x 2^0). 

Faktör a ^ 0 = 1 olduğundan, n_i = 0 olan tüm faktörleri yok sayabiliriz. İşlem, O (log n) time ve O (1) space (aşağıya bakınız) olan bir algoritma olarak yazılabilir.

Daha sonra, BigInteger 'ı kullanmaktan kaçınmak için bir meydan okuma olarak hesaplamayı iki bölüme ayırabiliriz: cevabı bulmak mod 2 ^ 10 ve cevabı bulmak < kod> mod 5 ^ 10 . Her iki durumda da, ilgili aralıklardaki sayılar ve ilgili aralıklardaki sayı ürünleri, long s değerlerine uyar. Dezavantajı, sonuçları tekrar birleştirmek için Çin Kalan Teoremi'ni kullanmamız gerektiğidir, ancak bu o kadar da zor değildir ve öğreticidir. Çince Kalan Teoremi kullanmanın en zor kısmı, tersine mod m bulmaktır, ancak bu, Öklid algoritmasının bir modifikasyonu kullanılarak basit bir şekilde gerçekleştirilebilir.

Asimptotik çalışma süresi O (n log n) , boşluk O (1) ve her şey birkaç uzun değişkene uyar, BigInteger yok veya gerekli diğer sofistike kütüphane.

public class SeriesMod1010 {

  public static long pow(long a,long n,long m) {//a^n mod m
    long result = 1;
    long a2i = a%m;//a^2^i for i = 0, ...
    while (n>0) {
      if (n%2 == 1) {
    result *= a2i;
    result %= m;
      }
      a2i *= a2i;
      a2i %= m;
      n /= 2;
    }
    return result;
  }

  public static long inverse(long a, long m) {//mult. inverse of a mod m
    long r = m;
    long nr = a;
    long t = 0;
    long nt = 1;
    long tmp;
    while (nr != 0) {
      long q = r/nr;
      tmp = nt; nt = t - q*nt; t = tmp;
      tmp = nr; nr = r - q*nr; r = tmp;
    }
    if (r > 1) return -1;//no inverse
    if (t < 0) t += m;
    return t;
  }

  public static void main(String[] args) {
    long twoTo10 = 1024;
    long sum210 = 0;
    for (long i=1; i<=1000; i++) {
      sum210 += pow(i,i,twoTo10);
      sum210 %= twoTo10;
    }

    long fiveTo10 = 9_765_625;
    long sum510 = 0;
    for (long i=1; i<=1000; i++) {
      sum510 += pow(i,i,fiveTo10);
      sum510 %= fiveTo10;
    }

   //recombine the numbers with the Chinese remainder theorem
    long tenTo10 = 10_000_000_000L;
    long answer = sum210 * inverse(fiveTo10,twoTo10) * fiveTo10
      + sum510 * inverse(twoTo10,fiveTo10) * twoTo10;
    answer %= tenTo10;
    System.out.println(answer);
  }

}
1
katma
Çok iyi teşekkürler!
katma yazar Alex Salauyou, kaynak
n_i n'in ikilik hanesidir, sağ ucunda sıfırıncı haneyle birlikte.
katma yazar Edward Doolittle, kaynak
Bu iyi bir algoritma gibi görünüyor. N_i'nin ne anlama geldiği farz edilir? göstermek için bir yol n * i?
katma yazar Jason, kaynak

BigInteger olmadan çözülebilir, çünkü taşmayı önlemek için % kullanarak her toplama veya çarpma işleminde yalnızca son 10 rakam saklamanız gerekir:

int n = 1000;
long result = 0;
long tenDigits = 10_000_000_000L;
for (int i = 1; i <= n; i++) {
    long r = i;
    for (int j = 2; j <= i; j++) {
        r = (r * i) % tenDigits;
    }
    result += r;
}  
return result % tenDigits;

Karmaşıklık, O'nun (N ^ 2) olduğunu, çarpımın sabit sürede çalıştığını varsayalım.

Cevap: 9110846700.

0
katma
Doğru, r * i 'nin en büyük sonucu 3 + 10 = 13 hane ile sınırlıdır.
katma yazar Peter Lawrey, kaynak
BigInteger kullanıyorsanız, modPow kullanmanın daha etkili olduğundan şüpheleniyorum. ;)
katma yazar Peter Lawrey, kaynak
Long.MAX_VALUE 9,223,372,036,854,775,807, toplam 19 hanedir, ancak 19 hane için tüm olası değerler değildir, bu nedenle yalnızca 18 hane güvenlidir.
katma yazar Peter Lawrey, kaynak
Bu, r ^ n değerini hesaplamak yerine r değerinin karesini almaya devam edecektir. Ayrıca 9,999,999,999 ^ 2 de taşacaktır.
katma yazar Peter Lawrey, kaynak
@PeterLawrey düzeltildi: r = (r * r) yerine r = (r * i)
katma yazar Alex Salauyou, kaynak
Yorumunuzda uzun taşma konusunda haklısınız, ancak kodumda asla olamaz, çünkü oraya kareler çekmem. Her çarpma işleminden sonra sonuç kesilir.
katma yazar Alex Salauyou, kaynak

Bu aşırı hesaplamalar yapmadan doğru cevap verir. Uzun bir yeter.

public String lastTen() {
        long answer = 0;
        String txtAnswer = "";
        int length = 0;
        int i = 1;

        for(i = 1; i <= 1000; i++) {
            answer += Math.pow(i, i);
            txtAnswer = Long.toString(answer);
            length = txtAnswer.length();
            if(length > 9) break;
        }
        return txtAnswer.substring(length-10);
    }
0
katma

The decimal base uses 0...9 (10 digits) to represent digits, a number that is in the second position right to left represents Digits * base.length^l2rPosition. Using this logics you can create a class that "pretty much does what your primary school teacher told you to, back when we used paper to calculate stuff, but with a baseN number and base-to-base conversions" I have done this class fully functional in C#, but I don't have time to translate it completely to java, this is about the same logics behind java.math.BigInteger. (with less performance I bet for I used a lot of lists >_>" No time to optimize it now

class IntEx {
    ArrayList digits = new ArrayList<>();
    long baseSize = Integer.MAX_VALUE+1;
    boolean negative = false;

    public IntEx(int init)
    {
        set(init);
    }

    public void set(int number)
    {
        digits = new ArrayList<>();
        int backup = number;
        do
        {
            int index = (int)(backup % baseSize);
            digits.add(index);
            backup = (int) (backup/baseSize);
        } while ((backup) > 0);
    }

   //... other operations
    private void add(IntEx number)
    {
        IntEx greater = number.digits.size() > digits.size() ? number : this;
        IntEx lesser = number.digits.size() < digits.size() ? number : this;
        int leftOvers = 0;
        ArrayList result = new ArrayList<>();
        for (int i = 0; i < greater.digits.size() || leftOvers > 0; i++)
        {
            int sum;
            if (i >= greater.digits.size())
                sum = leftOvers;
            else if(i >= lesser.digits.size())
                sum = leftOvers + greater.digits.get(i);
            else
                sum = digits.get(i) + number.digits.get(i) + leftOvers;
            leftOvers = 0;
            if (sum > baseSize-1)
            {
                while (sum > baseSize-1)
                {
                    sum -= baseSize;
                    leftOvers += 1;
                }
                result.add(sum);
            }
            else
            {
                result.add(sum);
                leftOvers = 0;
            }
        }
        digits = result;
    }
    private void multiply(IntEx target)
    {
        ArrayList MultiParts = new ArrayList<>();
        for (int i = 0; i < digits.size(); i++)
        {
            IntEx thisPart = new IntEx(0);
            thisPart.digits = new ArrayList<>();
            for (int k = 0; k < i; k++)
                thisPart.digits.add(0);
            int Leftovers = 0;
            for (int j = 0; j < target.digits.size(); j++)
            {
                int multiFragment = digits.get(i) * (int) target.digits.get(j) + Leftovers;
                Leftovers = (int) (multiFragment/baseSize);
                thisPart.digits.add((int)(multiFragment % baseSize));
            }
            while (Leftovers > 0)
            {
                thisPart.digits.add((int)(Leftovers % baseSize));
                Leftovers = (int) (Leftovers/baseSize);
            }
            MultiParts.add(thisPart);
        }
        IntEx newNumber = new IntEx(0);
        for (int i = 0; i < MultiParts.size(); i++)
        {
            newNumber.add(MultiParts.get(i));
        }
        digits = newNumber.digits;
    }

    public long longValue() throws Exception
    {
        int position = 0;
        long multi = 1;
        long retValue = 0;
        if (digits.isEmpty()) return 0;
        if (digits.size() > 16) throw new Exception("The number within IntEx class is too big to fit into a long");
        do
        {
            retValue += digits.get(position) * multi;
            multi *= baseSize;
            position++;
        } while (position < digits.size());
        return retValue;
    }

    public static long BaseConvert(String number, String base)
    {
        boolean negative = number.startsWith("-");
        number = number.replace("-", "");
        ArrayList localDigits = new ArrayList<>();
        for(int i = number.toCharArray().length - 1; i >=0; i--) {
            localDigits.add(number.charAt(i));
        }
       //List<>().reverse is missing in this damn java. -_-
        long retValue = 0;
        long Multi = 1;
        char[] CharsBase = base.toCharArray();
        for (int i = 0; i < number.length(); i++)
        {
            int t = base.indexOf(localDigits.get(i));
            retValue += base.indexOf(localDigits.get(i)) * Multi;
            Multi *= base.length();
        }
        if (negative)
            retValue = -retValue;
        return retValue;
    }

    public static String BaseMult(String a, String b, String Base)
    {
        ArrayList MultiParts = new ArrayList<>();
       //this huge block is a tribute to java not having "Reverse()" method.
        char[] x = new char[a.length()];
        char[] y = new char[b.length()];
        for(int i = 0; i < a.length(); i++) {
            x[i] = a.charAt(a.length()-i);
        }
        for(int i = 0; i < b.length(); i++) {
            y[i] = a.charAt(a.length()-i);
        }
        a = new String(x);
        b = new String(y);
       //---------------------------------------------------------------------
        for (int i = 0; i < a.length(); i++)
        {
            ArrayList thisPart = new ArrayList<>();
            for (int k = 0; k < i; k++)
                thisPart.add(Base.charAt(0));
            int leftOvers = 0;
            for (int j = 0; j < b.length(); j++)
            {
               //Need I say repeated characters in base may cause mayhem?
                int MultiFragment = Base.indexOf(a.charAt(i)) * Base.indexOf(b.charAt(j)) + leftOvers;
                leftOvers = MultiFragment/Base.length();
                thisPart.add(Base.charAt(MultiFragment % Base.length()));
            }
            while (leftOvers > 0)
            {
                thisPart.add(Base.charAt(leftOvers % Base.length()));
                leftOvers = leftOvers/Base.length();
            }
            char[] thisPartReverse = new char[thisPart.size()];
            for(int z = 0; z < thisPart.size();z++)
                thisPartReverse[z] = thisPart.get(thisPart.size()-z);
            MultiParts.add(new String(thisPartReverse));
        }
        String retValue = ""+Base.charAt(0);
        for (int i = 0; i < MultiParts.size(); i++)
        {
            retValue = BaseSum(retValue, MultiParts.get(i), Base);
        }
        return retValue;
    }

    public static String BaseSum(String a, String b, String Base)
    {
       //this huge block is a tribute to java not having "Reverse()" method.
        char[] x = new char[a.length()];
        char[] y = new char[b.length()];
        for(int i = 0; i < a.length(); i++) {
            x[i] = a.charAt(a.length()-i);
        }
        for(int i = 0; i < b.length(); i++) {
            y[i] = a.charAt(a.length()-i);
        }
        a = new String(x);
        b = new String(y);
       //---------------------------------------------------------------------
        String greater = a.length() > b.length() ? a : b;
        String lesser = a.length() < b.length() ? a : b;
        int leftOvers = 0;
        ArrayList result = new ArrayList();
        for (int i = 0; i < greater.length() || leftOvers > 0; i++)
        {
            int sum;
            if (i >= greater.length())
                sum = leftOvers;
            else if (i >= lesser.length())
                sum = leftOvers + Base.indexOf(greater.charAt(i));
            else
                sum = Base.indexOf(a.charAt(i)) + Base.indexOf(b.charAt(i)) + leftOvers;
            leftOvers = 0;
            if (sum > Base.length()-1)
            {
                while (sum > Base.length()-1)
                {
                    sum -= Base.length();
                    leftOvers += 1;
                }
                result.add(Base.charAt(sum));
            }
            else
            {
                result.add(Base.charAt(sum));
                leftOvers = 0;
            }
        }
        char[] reverseResult = new char[result.size()];
        for(int i = 0; i < result.size(); i++)
            reverseResult[i] = result.get(result.size() -i);
        return new String(reverseResult);
    }

    public static String BaseConvertItoA(long number, String base)
    {
        ArrayList retValue = new ArrayList<>();
        boolean negative = false;
        long backup = number;
        if (negative = (backup < 0))
            backup = -backup;
        do
        {
            int index = (int)(backup % base.length());
            retValue.add(base.charAt(index));
            backup = backup/base.length();
        } while ((backup) > 0);
        if (negative)
            retValue.add('-');
        char[] reverseRetVal = new char[retValue.size()];
        for(int i = 0; i < retValue.size(); i++)
            reverseRetVal[i] = retValue.get(retValue.size()-i);
        return new String(reverseRetVal);
    }

    public String ToString(String base)
    {
        if(base == null || base.length() < 2)
            base = "0123456789";
        ArrayList retVal = new ArrayList<>();
        char[] CharsBase = base.toCharArray();
        int TamanhoBase = base.length();
        String result = ""+base.charAt(0);
        String multi = ""+base.charAt(1);
        String lbase = IntEx.BaseConvertItoA(baseSize, base);
        for (int i = 0; i < digits.size(); i++)
        {
            String ThisByte = IntEx.BaseConvertItoA(digits.get(i), base);
            String Next = IntEx.BaseMult(ThisByte, multi, base);
            result = IntEx.BaseSum(result, Next, base);
            multi = IntEx.BaseMult(multi, lbase, base);
        }
        return result;
    }

    public static void main(String... args) {
        int ref = 0;
        IntEx result = new IntEx(0);
        while(++ref <= 1000)
        {
            IntEx mul = new IntEx(1000);
            for (int i = 0; i < 1000; ++i) {
                mul.multiply(new IntEx(i));
            }
            result.add(mul);
        }
        System.out.println(result.toString());
    }
}

Feragatname: Bu bir C# çalışmasının kaba bir çevirisi/yerelleştirmesidir, ihmal edilen birçok kod vardır. Bu "neredeyse" java.math.BigInteger'ın arkasındaki aynı mantıklardır (BigInteger kodunu favori tasarımcınıza açabilir ve kendinize bakabilirsiniz. , bu örnek sadece teorinin "belki" bir açıklaması için.

Ayrıca, sadece bir genel yazı, "tekerleği yeniden icat etmeye çalışmak" olduğunu biliyorum, ancak bu sorunun akademik bir amacı olduğunu düşünerek paylaşmanın oldukça kolay olduğunu düşünüyorum. Biri bu çalışmanın sonucunu gitHub (yerelleştirilmemiş) adresinde görebilir, bu C #’yı genişletmiyorum Bu sorunun kodunu, çok geniş ve bu dilin dili için kodlayın.

0
katma

BigIntegers kullanın:

    import java.math.BigInteger;

public class Program {

    public static void main(String[] args) {
        BigInteger result = new BigInteger("1");
        BigInteger temp = new BigInteger("1");
        BigInteger I;
        for(int i = 1 ; i < 1001 ; i++){
            I = new BigInteger(""+i);
            for(int j = 1 ; j < i ; j++){
                temp = temp.multiply(I);
            }
            result = result.multiply(temp);
            temp = new BigInteger("1");
        }
        System.out.println(result);
    }
}
0
katma