niedziela, lipca 27, 2008

Pomnóżmy sobie duże liczby ;-)

Licząc coś wczoraj przez chwilę myślałem, że złe wyniki mnożenia to wina zaokrągleń w BigDecimal'u, okazało się, że byłem w błędzie i wina leżała nie po stronie BigDecimal'a a dostarczonej wcześniej wartości ;-)
Jednak zanim doszedłem do tego, że BigDecimal nic mi nie zaokrąglił stworzyłem sobie kod do mnożenia liczb o rozmiarach ograniczonych tylko przez ilość dostępnej pamięci ;-) [działa dokładnie tak jak mnożenie BigDecimal'em ;-), ale jest moje :-)]
  public String myMultiply(String x1,String x2) {
    if (x1.indexOf(".")==-1x1=x1+".0";
    if (x2.indexOf(".")==-1x2=x2+".0";
    Map res = new HashMap() {
      @Override
      public Byte get(Object key) {
        Byte o = super.get(key);
        return (o!=null)?o:(Byte.valueOf((byte)0));
      }
    };
    x1 = reverseString(x1);
    x2 = reverseString(x2);
    int dotPos = (x1.indexOf("."))+(x2.indexOf("."));
    x1 = x1.replaceAll("\\.""");
    x2 = x2.replaceAll("\\.""");
    for (int i=0; i(); i++) {
      for (int j=0; j(); j++) {
        int pos = i+j;
        int numA = Byte.valueOf(""+x1.charAt(i));
        int numB = Byte.valueOf(""+x2.charAt(j));
        int newPos = pos;
        int rest = 0;
        int subRes = numA*numB;
        do {
          int curVal = res.get(newPos);
          int newVal = (subRes+curVal)%10;
          rest = ((subRes+curVal- newVal)/10;
          subRes = rest;
          res.put(newPos,(byte)newVal);
          newPos++;
        while (rest!=0);
      }
    }
    String result = "";
    for (int i=0; i(); i++) {
      result+=""+res.get(i);
    }
    result = result.substring(0,dotPos)+"."+result.substring(dotPos);
    int pos = result.length()-1;
    while (result.charAt(pos)=='0') {
      pos--;
    }
    if (result.charAt(pos)=='.'pos++;
    result = result.substring(0,pos+1);
    result = reverseString(result);
    return result;
  }
  private String reverseString(String x) {
    String newX = "";
    for (int idx=0; idx(); idx++) {
      newX=x.charAt(idx)+newX;
    }
    return newX;
  }
[kod pokolorowany przy pomocy Java2HTML convertera]
Algorytm stojący za tym mnożeniem to zwykłe mnożenie pod kreskę ;-)


Podobne postybeta
Swing - największe zło Java'y ;-)
Potfór ;-) czyli generator z yield w Java'ie
Monitorujemy cenę IntelliJ'a ;-)
Potworność ;-) czyli mnożenie w 90 liniach ;-)
Czy się stoi czy się siedzi... Rasbperry Pi z czujnikami ultradźwiękowymi to stwierdzi ;-)