Applet de factorizacion de enteros gausianos

Iniciado por ProcessKill, Febrero 24, 2010, 04:24:03 PM

Tema anterior - Siguiente tema

0 Miembros y 1 Visitante están viendo este tema.

Febrero 24, 2010, 04:24:03 PM Ultima modificación: Abril 18, 2013, 12:44:52 PM por Expermicid
Applet de factorizacion de enteros gausianos

Código: java
// <XMP>
// Gaussian Integer factorization applet
//
// Written by Dario Alejandro Alpern (Buenos Aires - Argentina)
// Last updated May 31st, 2002, See http://www.alpertron.com.ar/GAUSIANO.HTM
//
// No part of this code can be used for commercial purposes without
// the written consent from the author. Otherwise it can be used freely
// except that you have to write somewhere in the code this header.
//
import java.applet.*;
import java.util.*;
import java.awt.*;
import java.math.*;

public final class gausiano extends Applet implements Runnable {

private BigInteger Primes[];
private int Exponents[];
private BigInteger Solution1[];
private BigInteger Solution2[];
private BigInteger Increment[];
private BigInteger Aux[];
private BigInteger ValA, ValB;
private StringBuffer info;
private String txt;
private int SolNbr;
private Frame factorWindow;
private ecmc factorPanel;
private volatile Thread calcThread;
private BigInteger LastModulus = BigInteger.valueOf(0);
private int Ind;
private String textError;

void w(String texto) {
  info=info.append(texto);
  }

void Solution(BigInteger value) {
  SolNbr++;
  w(SolNbr+") x = "+value.toString()+"<BR>");
  }

public void init() {
  Primes=new BigInteger[400];
  Exponents=new int[400];
  Solution1=new BigInteger[400];
  Solution2=new BigInteger[400];
  Increment=new BigInteger[400];
  Aux=new BigInteger[400];
  }

/* type = 0: factor expression, type = 1: just compute expression */
public String startCalc(String expr, int type) {
  String InputField;
  if (calcThread != null) {
//    TerminateThread = true;
    try {
      calcThread.join();        /* Wait until the solving thread dies */
      } catch (InterruptedException ie) {};
    }
  calcThread = new Thread(this);  /* Start solving thread */
  try {
    int ExpressionRC;
    BigInteger [] ExpressionResult = new BigInteger[2];
    InputField = expr.trim();
    if (InputField.equals("")) {
      ExpressionRC = -6;
      }
    try {
      ExpressionRC = GaussExpression.ComputeExpression(InputField, ExpressionResult);
      } catch (OutOfMemoryError e) {ExpressionRC = -1;}
    switch (ExpressionRC) {
      case -1:
        textError = "No hay suficiente memoria.";
        break;
      case -2:
        textError = "Número muy grande (más de 500 dígitos).";
        break;
      case -3:
        textError = "Expresión intermedia con más de 2000 dígitos.";
        break;
      case -4:
        textError = "División no entera.";
        break;
      case -5:
        textError = "Error de paréntesis.";
        break;
      case -6:
        textError = "Error de sintaxis.";
        break;
      case -7:
        textError = "Demasiados paréntesis.";
        break;
      case -8:
        textError = "Parámetro inválido.";
        break;
      default:
        if (ExpressionResult[0].compareTo(BigInteger.valueOf(10L).pow(500))>=0) {
          textError = "Número muy grande (más de 500 dígitos).";
          }
        else {
          textError = "";
          }
      }
    if (textError.length() > 0) {return textError;}
    ValA = ExpressionResult[0];
    ValB = ExpressionResult[1];
    } catch (Exception e) {return "Se entraron datos inválidos";}
  if (type == 1) {     /* Only computing expression */
    info=new StringBuffer();
    w("<HTML><HEAD><TITLE>Calculadora de enteros gausianos</TITLE></HEAD><BODY>");
    w("<CENTER><H3><FONT COLOR=Red>Calculadora de enteros gausianos</FONT></H3></CENTER>");
    w("<P><I>por Dario Alejandro Alpern</I><P><DL><DT>Expresión de entrada:<DD>");
    w(InputField);
    w("<P><DT>Valor:<DD>");
    w(ValA.toString()+(ValB.signum()>=0?" + ":" - ")+ValB.abs().toString()+" i</DL>");
    w("<P>Si encontró algún error, por favor envíeme un <A HREF=\"mailto:[email protected]?subject=Factorizacion de enteros de Gauss\">e-mail</A><P>");
    w("<A HREF=\"GBOOK.HTM\">Apriete aquí</A> para ver o firmar mi libro de invitados.</BODY></HTML>");
    return info.toString();
    }
  calcThread.start();
  return "";
  }

public String resultCalc() {
  if (calcThread == null) {
    return info.toString();
    }
  return "";
  }

public void run() {
  String parms1[];
  StringBuffer parms2[];
  parms1=new String[0];
  parms2=new StringBuffer[1];
  info=new StringBuffer();
  w("<TITLE>Applet de factorizacion de enteros de Gauss</TITLE><CENTER><FONT COLOR=Red><B>");
  w("Factores primos de "+ValA.toString()+(ValB.signum()>=0?" + ":" - ")+ValB.abs().toString()+" i</B></FONT></CENTER><P><I>por Dario Alejandro Alpern</I><P>");
  Date OldDate=new Date();
  long Old=OldDate.getTime();
  SolNbr = 0;
  GaussianFactorization();
  Date NewDate=new Date();
  long New=NewDate.getTime();
  w("<P>Tiempo de cálculo: ");
  int t=(int)(((New-Old)/1000+86400)%86400);
  w(t/3600+"h "+((t%3600)/60)+"m "+(t%60)+"s");
  w("<P>Si encontró algún error, por favor envíeme un <A HREF=\"mailto:[email protected]?subject=Factorizacion de enteros de Gauss\">e-mail</A><P>");
  w("<A HREF=\"GBOOK.HTM\">Apriete aquí</A> para ver o firmar mi libro de invitados.</BODY></HTML>");
  calcThread = null;
  }

void GaussianFactorization() {
  BigInteger BigInt0, BigInt1, BigInt2;
  BigInt0 = BigInteger.valueOf(0L);
  BigInt1 = BigInteger.valueOf(1L);
  BigInt2 = BigInteger.valueOf(2L);
  BigInteger K, Mult1, Mult2, p, q, M1, M2, Tmp;
  int index, index2;

  BigInteger norm = ValA.multiply(ValA).add(ValB.multiply(ValB));
  Ind = 0;
  if (norm.signum() == 0) {
    w("Cualquier primo gausiano divide este número");
    return;
    }
  w("<UL>");
  if (norm.compareTo(BigInt1) > 0) {
    if (norm.bitLength() < 32) {
      long modulus = norm.longValue();
      int Exp = 0;
      Ind = 0;
      while (modulus % 2 == 0) {
        Exp++;
        modulus /= 2;
        }
      if (Exp > 0) {
        Primes[0] = BigInt2;
        Exponents[0] = Exp;
        Ind++;
        }
      long Div = 3;
      while (Div*Div <= modulus) {
        Exp = 0;
        while (modulus % Div == 0) {
          Exp++;
          modulus /= Div;
          }
        if (Exp > 0) {
          Primes[Ind] = BigInteger.valueOf(Div);
          Exponents[Ind] = Exp;
          Ind++;
          }
        Div += 2;
        }
      if (modulus > 1) {
        Primes[Ind] = BigInteger.valueOf(modulus);
        Exponents[Ind] = 1;
        Ind++;
        }
      }
    else {     /* Factor norm > 2^32 */
      factorPanel = new ecmc();
      factorWindow = new Frame("Factorizacion de la norma");
      factorWindow.setResizable(false);
      factorWindow.add(factorPanel);
      factorPanel.setSize(600, 390);
      Insets in = factorWindow.getInsets();
      factorWindow.setSize(600+in.right+in.left, 390+in.top+in.bottom);
      factorWindow.show();
      Ind = factorPanel.getFactors(norm, Primes, Exponents);
      factorWindow.remove(factorPanel);
      factorWindow.dispose();
      }
    for (index = 0; index < Ind; index++) {
      p = Primes[index];
      if (p.equals(BigInt2)) {
        for (index2 = 0; index2 < Exponents[index]; index2++) {
          DivideGaussian(BigInt1, BigInt1);           /* Divide by 1+i */
          DivideGaussian(BigInt1, BigInt1.negate());  /* Divide by 1-i */
          }
        }
      if (p.testBit(1) == false) {    /* if p = 1 (mod 4) */
        q = p.subtract(BigInt1);      /* q = p-1 */
        K = BigInt1;
        do {                 // Compute Mult1 = sqrt(-1) mod p
          K = K.add(BigInt1);
          Mult1 = K.modPow(q.shiftRight(2),p);
          } while (Mult1.equals(BigInt1) || Mult1.equals(q));
        Mult2 = BigInt1;
        while (true) {
          K = Mult1.multiply(Mult1).add(Mult2.multiply(Mult2)).divide(p);
          if (K.equals(BigInt1)) {
            break;
            }
          M1 = Mult1.mod(K);
          M2 = Mult2.mod(K);
          if (M1.compareTo(K.shiftRight(1)) > 0) {M1 = M1.subtract(K);}
          if (M2.compareTo(K.shiftRight(1)) > 0) {M2 = M2.subtract(K);}
          Tmp = Mult1.multiply(M1).add(Mult2.multiply(M2)).divide(K);
          Mult2 = Mult1.multiply(M2).subtract(Mult2.multiply(M1)).divide(K);
          Mult1 = Tmp;
          }            /* end while */
        if (Mult1.abs().compareTo(Mult2.abs()) < 0) {
          Tmp = Mult1;
          Mult1 = Mult2;
          Mult2 = Tmp;
          }
        for (index2 = 0; index2 < Exponents[index]; index2++) {
          DivideGaussian(Mult1,Mult2);
          DivideGaussian(Mult1,Mult2.negate());
          }
        }              /* end p = 1 (mod 4) */
      else {           /* if p = 3 (mod 4) */
        for (index2 = 0; index2 < Exponents[index]; index2++) {
          DivideGaussian(Primes[index],BigInt0);
          }            /* end p = 3 (mod 4) */
        }
      }
    }
  if (ValA.equals(BigInt1)) {
    if (Ind == 0) {
      w("Ningún primo gausiano divide este número");
      }
    }
  else if (ValA.add(BigInt1).signum() == 0) {
    w("<LI>-1");
    }
  else if (ValB.equals(BigInt1)) {
    w("<LI>i");
    }
  else {
    w("<LI>-i");
    }
  w("</UL>");
  }

private void DivideGaussian(BigInteger real, BigInteger imag) {
  real = real.abs();
  BigInteger norm = real.multiply(real).add(imag.multiply(imag));
  BigInteger realNum = ValA.multiply(real).add(ValB.multiply(imag));
  BigInteger imagNum = ValB.multiply(real).subtract(ValA.multiply(imag));
  if (realNum.mod(norm).signum() == 0 &&
      imagNum.mod(norm).signum() == 0) {
    ValA = realNum.divide(norm);
    ValB = imagNum.divide(norm);
    w("<LI>");
    w(real.toString()+(imag.signum()>=0?" + ":" - ")+imag.abs().toString()+" i");
    }
  }
}


Espero que les sirva el code  ;D Saludos