Adição de números extremamente grandes no shell script

8

Suponha que dois números sejam armazenados em dois arquivos diferentes, a.txte b.txt.

Cada número é grande o suficiente (mais de 30 dígitos) para não ser suportado pelo tipo de dados numérico usado por bash.

Como posso adicioná-los no shell?

voldemort619
fonte
Pessoalmente, eu usaria pythonou similar nesse caso.
PHK
Tem certeza de que não deseja usar o sed para adição ?
Jeff Schaller
Há algum tempo, na minha classe java, usamos pilhas para adicionar números que estavam fora do intervalo max int do java. Supondo que você esteja disposto a se dar ao trabalho de implementar a pilha usando matrizes no bash, você pode fazer isso. . . mas é muito redundante. . . e desnecessário, como você pode ver nas respostas abaixo. Ou apenas use pythoncomo phk sugerido #
Sergiy Kolodyazhnyy

Respostas:

12

Supondo que sejam números decimais, você pode:

paste -d + a.txt b.txt | bc

Cuidado bccom os agrupamentos de linha de números muito longos (mais de 68 ou 69 dígitos, dependendo da implementação). Com o GNU bc, você pode desativá-lo configurando a BC_LINE_LENGTHvariável de ambiente como 0, como em:

paste -d + a.txt b.txt | BC_LINE_LENGTH=0 bc
Stéphane Chazelas
fonte
10

O truque é não usar bashpara executar a adição 1 .

Primeiro, leia cada número em uma variável separada. Isso pressupõe que os arquivos contenham apenas um número e nenhuma outra informação.

a="$(<a.txt)"
b="$(<b.txt)"

Em seguida, use a bccalculadora para obter o resultado:

bc <<<"$a + $b"

bc é uma "linguagem e calculadora aritmética de precisão arbitrária".

Para armazenar o resultado em uma variável c:

c="$( bc <<<"$a + $b" )"

Se a <<<sintaxe parecer estranha (é chamada de "string aqui" e é uma extensão da sintaxe do shell POSIX suportada por bashe mais algumas conchas), você pode usar printfpara enviar a adição para bc:

printf '%s + %s\n' "$a" "$b" | bc

E armazenando o resultado cnovamente:

c="$( printf '%s + %s\n' "$a" "$b" | bc )"

1 Usar bashpara realizar a adição de dois números extremamente grandes exigiria a implementação, no bashscript, de uma rotina para executar aritmética de precisão arbitrária . Isso é perfeitamente factível, mas complicado e desnecessário, pois todos os Unix bcque já oferecem esse serviço já são fornecidos de maneira relativamente fácil e acessível.

Kusalananda
fonte
1
Alternativamente, você poderia fazer read a < a.txt. Isso também resolveria eliminar espaços em branco à esquerda e à direita, se houver (assumindo $IFSque não foram modificados).
Stéphane Chazelas
1
Por que as aspas dentro das aspas não precisam ser escapadas para a string here dentro da substituição do processo?
Bryce Guinta
2
@BryceGuinta Porque, diferentemente de algo como echo "\"hello\"", a coisa dentro do $(...)não é uma string passada como argumento para outro programa, e o shell sabe como lidar com o aninhamento de aspas. É também por isso que usar em $(...)vez de reticulares é melhor; você pode escrever $( ... $( ... ) )sem ambiguidade, enquanto a mesma coisa usando backticks é ... estranha.
Kusalananda
mas como fazer em bash não usar bc
voldemort619
@ voldemort619 Você precisaria implementar a adição de maneira semelhante a qualquer uma dessas bibliotecas . Você pode dar uma olhada nesta resposta do StackOverflow para obter uma explicação. Mas sério, basta usar bc.
Kusalananda
3

Como Stéphane e Kusalananda disseram , "realmente, basta usar bc", mas se você realmente deseja usar o bash para adição, aqui está um ponto de partida (apenas números inteiros positivos) - deixarei como um exercício para o leitor implementar decimais e números negativos:

function arbadd {
  addend1=$1
  addend2=$2
  sum=
  bcsum=$(echo $addend1 + $addend2 | BC_LINE_LENGTH=0 bc)

  # zero-pad the smallest number
  while [ ${#addend1} -lt ${#addend2} ]
  do
    addend1=0${addend1}
  done

  while [ ${#addend2} -lt ${#addend1} ]
  do
    addend2=0${addend2}
  done

  carry=0
  for((index=${#addend1}-1;index >= 0; index--))
  do
    case ${carry}${addend1:index:1}${addend2:index:1} in
      (000) carry=0; sum=0${sum};;
      (001|010|100) carry=0; sum=1${sum};;
      (002|011|020|101|110) carry=0; sum=2${sum};;
      (003|012|021|030|102|111|120) carry=0; sum=3${sum};;
      (004|013|022|031|040|103|112|121|130) carry=0; sum=4${sum};;
      (005|014|023|032|041|050|104|113|122|131|140) carry=0; sum=5${sum};;
      (006|015|024|033|042|051|060|105|114|123|132|141|150) carry=0; sum=6${sum};;
      (007|016|025|034|043|052|061|070|106|115|124|133|142|151|160) carry=0; sum=7${sum};;
      (008|017|026|035|044|053|062|071|080|107|116|125|134|143|152|161|170) carry=0; sum=8${sum};;
      (009|018|027|036|045|054|063|072|081|090|108|117|126|135|144|153|162|171|180) carry=0; sum=9${sum};;
      (019|028|037|046|055|064|073|082|091|109|118|127|136|145|154|163|172|181|190) carry=1; sum=0${sum};;
      (029|038|047|056|065|074|083|092|119|128|137|146|155|164|173|182|191) carry=1; sum=1${sum};;
      (039|048|057|066|075|084|093|129|138|147|156|165|174|183|192) carry=1; sum=2${sum};;
      (049|058|067|076|085|094|139|148|157|166|175|184|193) carry=1; sum=3${sum};;
      (059|068|077|086|095|149|158|167|176|185|194) carry=1; sum=4${sum};;
      (069|078|087|096|159|168|177|186|195) carry=1; sum=5${sum};;
      (079|088|097|169|178|187|196) carry=1; sum=6${sum};;
      (089|098|179|188|197) carry=1; sum=7${sum};;
      (099|189|198) carry=1; sum=8${sum};;
      (199) carry=1; sum=9${sum};;
    esac
  done
  if [ $carry -eq 1 ]
  then
    sum=1${sum}
  fi
  printf "Sum = %s\n" "$sum"
}

Eu deixei a bccomparação lá, mas comentei, para comparação.

Jeff Schaller
fonte