pab-h / expanded_number

Expanded Number

Um Expanded Number é a representação computacional de um número real expandido em suas somas multiplicadas por dez elevado a suas respectivas ordens.

Representação visual

(p₀)[m₀ o₀] -> ... -> (p_i)[m_i o_i] -> ... -> (p_n)[m_n o_n] -> λ

Onde p_i é a i-ésima parte, m_i é o i-ésimo módulo e o_i é a i-ésima ordem de um Expanded Number.

Uma parte é formada pelo seu módulo e a sua ordem.

Exemplos

1. Se 123 é um número real. Então, pode ser escrito como: 123 = 1x10² + 2x10¹ + 3x10⁰ Dessa forma, na representação Expanded Number será: (p₀)[3 0] -> (p₁)[2 1] -> (p₂)[1 2] -> λ

2. Se 10023 é um número real. Então, pode ser escrito como: 10023 = 1x10⁴ + 2x10¹ + 3x10⁰ Dessa forma, na representação Expanded Number será: (p₀)[3 0] -> (p₁)[2 1] -> (p₂)[1 4] -> λ

3. Se 100,23 é um número real. Então, pode ser escrito como: 100,23 = 1x10⁴ + 2x10^-1 + 3x10^-2 Dessa forma, na representação Expanded Number será: (p₀)[3 -2] -> (p₁)[2 -1] -> (p₂)[1 4] -> λ

Operações

Normalização

Normaliza um Expanded Number.

Exemplos de Expanded Number não normalizado:

• (p₀)[18 0] -> (p₁)[3 1] -> λ
• (p₀)[123 0] -> (p₁)[47 1] -> λ

Exemplos acima normalizado:

• (p₀)[8 0] -> (p₁)[4 1] -> λ
• (p₀)[3 0] -> (p₁)[9 1] -> (p₂)[5 2] -> λ

Em código, o equivalente será:

Expanded_Number *normalize_expanded_number(Expanded_Number *number) {
    Expanded_Number *tmp = create_expanded_number(); 
    Expanded_Number_Part *current = number->head;

    unsigned int current_module;
    int current_order;

    while (current) {
        current_module = current->module;
        current_order = current->order;

        while (current_module > 0){
            append_expanded_number_part(
                tmp, 
                current_module % 10, 
                current_order
            );

            current_module /= 10;
            current_order++;

        }

        current = current->next;
    }

    Expanded_Number *result = create_expanded_number(); 

    current = tmp->head;

    while (current) {
        if (
            is_empty_expanded_number(result) || 
            result->tail->order != current->order
        ) {
            append_expanded_number_part(
                result, 
                current->module, 
                current->order
            );
            current = current->next;
            
            continue;
        }

        if (result->tail->order == current->order) {
            result->tail->module += current->module;

        }

        current = current->next;
    }

    destroy_expanded_number(tmp);

    if (!is_normalized_expanded_number(result)) {

        return normalize_expanded_number(result);
    }

    return result;
}

Soma

Seja a = (p₀)[2 0] -> (p₁)[7 2] -> λ

Seja b = (p₀)[4 0] -> (p₁)[3 1] -> λ

Então, a soma a + b será:

a + b = (p₀)[6 0] -> (p₁)[3 1] -> (p₂)[7 2] -> λ

Em código, o equivalente será:

Expanded_Number *sum_expanded_number(Expanded_Number *a, Expanded_Number *b) {
    Expanded_Number *tmp = create_expanded_number();

    Expanded_Number_Part *current_a = a->head;
    Expanded_Number_Part *current_b = b->head;

    while (current_a || current_b) {
        if (current_a) {
            append_expanded_number_part(
                tmp, 
                current_a->module, 
                current_a->order
            );

            current_a = current_a->next;

        }

        if (current_b) {
            append_expanded_number_part(
                tmp, 
                current_b->module, 
                current_b->order
            );

            current_b = current_b->next;

        }

    }

    Expanded_Number *result = normalize_expanded_number(tmp);
    destroy_expanded_number(tmp);

    return result;
}

Multiplicação

Seja a = (p₀)[2 0] -> λ

Seja b = (p₀)[3 0] -> (p₁)[3 1] -> λ

Então, a multiplicação a * b será:

a * b = (p₀)[6 0] -> (p₁)[6 1] -> λ

Expanded_Number *multiply_by_expanded_number_part(Expanded_Number *number, Expanded_Number_Part *part) {
    Expanded_Number *tmp = create_expanded_number();
    Expanded_Number_Part *current = number->head;

    while (current) {
        append_expanded_number_part(
            tmp,
            current->module * part->module,
            current->order + part->order
        );

        current = current->next;
    }

    Expanded_Number *result = normalize_expanded_number(tmp);
    destroy_expanded_number(tmp);

    return result;
}

Expanded_Number *multiply_expanded_number(Expanded_Number *a, Expanded_Number *b) {
    Expanded_Number *result = multiply_by_expanded_number_part(b, a->head);
    Expanded_Number *previous_result;
    Expanded_Number *tmp;

    Expanded_Number_Part *current = a->head->next;

    while (current) {
        previous_result = result;
        tmp = multiply_by_expanded_number_part(b, current);
        result = sum_expanded_number(previous_result, tmp);

        destroy_expanded_number(previous_result);
        destroy_expanded_number(tmp);

        current = current->next;

    }

    return result;
}

Aplicação: Fatorial

#include "../headers/expanded_number.h"

Expanded_Number *factorial_expanded_number(Expanded_Number *number) {
    Expanded_Number *result = create_expanded_number();
    append_expanded_number_part(result, 1, 0);

    if (is_empty_expanded_number(number)) {

        return result;
    }

    Expanded_Number *previous_result;

    Expanded_Number *increment = create_expanded_number();
    append_expanded_number_part(increment, 1, 0);

    Expanded_Number *current = create_expanded_number();
    append_expanded_number_part(current, 1, 0);
    Expanded_Number *previous_current;


    while (!is_equal_expanded_number(number, current)) {
        previous_result = result;
        previous_current = current;

        current = sum_expanded_number(previous_current, increment);
        result = multiply_expanded_number(previous_result, current);
        
        destroy_expanded_number(previous_result);
        destroy_expanded_number(previous_current);

    }

    return result;
}

int main() {

    Expanded_Number *number = create_from_int(100);

    Expanded_Number *factorial = factorial_expanded_number(number);

    describe_expanded_number(factorial);
    print_expanded_number(factorial);

    return 1;
}

Nesse exemplo, é calculado o fatorial de 100.

Como executar o exemplo do fatorial

Compilando o arquivo

make

Executando

make run_factorial

Limpar o diretório de build

make clean