CODEWITHSUNDEEP
postgresqlalgorithmplpgsql
ido klein
ido klein

Reputation: 135

How to perform cascade rounding in PostgreSQL?

Cascade rounding is an algorithm to round an array of floats while preserving their sum. How does one implements this algorithm in PostgreSQL?

Upvotes: 1

Views: 317

Answers (1)

klin
klin

Reputation: 121764

You can implement this function in plpgsql:

create or replace function cascade_rounding(float[])
returns int[] immutable language plpgsql as $$
declare
    fp_total float = 0;
    int_total int = 0;
    fp_value float;
    int_value int;
    result int[];
begin
    foreach fp_value in array $1 loop
        int_value := round(fp_value + fp_total) - int_total;
        fp_total := fp_total + fp_value;
        int_total := int_total + int_value;
        result := result || int_value;
    end loop;
    return result;
end $$;

select cascade_rounding(array[1.1, 1.2, 1.4, 1.2, 1.3, 1.4, 1.4])

 cascade_rounding
------------------
 {1,1,2,1,1,2,1}
(1 row)

Try the function in Db<>fiddle.

Update. You can apply the function to a column. Exemplary table:

create table my_table(id serial primary key, float_number float);
insert into my_table (float_number) 
select unnest(array[1.1, 1.2, 1.4, 1.2, 1.3, 1.4, 1.4])

Query: 

select 
    unnest(array_agg(id order by id)) as id,
    unnest(array_agg(float_number order by id)) as float_number,
    unnest(cascade_rounding(array_agg(float_number order by id))) as int_number
from my_table;

However, this is not a perfect solution. The query is quite complex and suboptimal.

In Postgres, you can create a custom aggregate with the intention of using it as a window function. It's not particularly difficult but requires some knowledge, see User-Defined Aggregates in the documentation.

create type cr_type as (int_value int, fp_total float, int_total int);

create or replace function cr_state(state cr_type, fp_value float)
returns cr_type language plpgsql as $$
begin
    state.int_value := round(fp_value + state.fp_total) - state.int_total;
    state.fp_total := state.fp_total + fp_value;
    state.int_total := state.int_total + state.int_value;
    return state;
end $$;

create or replace function cr_final(state cr_type)
returns int language plpgsql as $$
declare
begin
    return state.int_value;
end $$;

create aggregate cascade_rounding_window(float) (
    sfunc = cr_state,
    stype = cr_type,
    finalfunc = cr_final,
    initcond = '(0, 0, 0)'
);

Use the aggregate as a window function: 

select 
    id, 
    float_number, 
    cascade_rounding_window(float_number) over (order by id) as int_number
from my_table;

 id | float_number | int_number
----+--------------+------------
  1 |          1.1 |          1
  2 |          1.2 |          1
  3 |          1.4 |          2
  4 |          1.2 |          1
  5 |          1.3 |          1
  6 |          1.4 |          2
  7 |          1.4 |          1
(7 rows)

Db<>fiddle.

Upvotes: 2

Related Questions