CUMULATIVE CALCULATION APPARATUS, CUMULATIVE CALCULATION METHOD, AND PROGRAM
A cumulative calculation device according to an embodiment is a cumulative calculation device that, with respect to a column v=(v 1 , . . . , v n ) of n values divided into groups, calculates cumulation for each of the groups through an associative binary operation. The cumulative calculation device includes: a value conversion unit configured to convert v into v′=(v 1 ′, . . . , v n ′) (where v 1 ′=(v 1 , c i )) when c=(c 1 , . . . , c n ) is a column of values in which 1 corresponds to a head element of the group and 0 corresponds to elements other than the head element among elements v 1 , . . . , v n of v; a binary operation generation unit configured to generate a new binary operation for calculating a new pair (p, q) for two pairs (w, x) and (y, z) (where x, z ∈ {0, 1} using the binary operation; a cumulative calculation unit configured to calculate cumulation s 1 ′ (where s i ′ is cumulation from v 1 ′ to v i ′ from the new binary operation) by the new binary operation for i=1, . . . , n; and an output unit configured to extract a column u=(u 1 , . . . , u n ) of values indicating the cumulation for said each of the groups from each s i ′ (where i=1, . . . , n) and output the extracted u. The new binary operation sets an operation result of w and y by the binary operation to p when z=0, sets y to p when z=1, and sets a logical sum of x and z to q.
1 . A cumulative calculation device that, with respect to a column v=(v 1 , . . . , v n ) of n values divided into groups, calculates cumulation for each of the groups through an associative binary operation, the cumulative calculation device comprising:
a memory; and
a processor configured to:
form c=(c 1 , . . . , c n ) as a column of values in which 1 corresponds to a head element of a group and 0 corresponds to elements other than the head element among elements v 1 , . . . , v n of v;
convert v into v′=(v 1 ′, . . . , v n ′) (where v i ′=(v i , c i ));
generate a new binary operation for calculating a new pair (p, q) for two pairs (w x) and (y, z) (where x, z ∈ {0, 1}) using the binary operation;
calculate cumulation s i ′ (where s i ′ is cumulation from v i ′ to v i ′ by the new binary operation) by the new binary operation for i=1, . . . , n; and
extract a column u=(u 1 , . . . , u n ) of values indicating the cumulation for said each of the groups from each s i ′ (where i=1, . . . , n), and output the extracted u,
wherein the new binary operation sets an operation result of w and y by the binary operation to p when z=0, sets y to p when z=1, and sets a logical sum of x and z to q.
2 . The cumulative calculation device according to claim 1 , wherein the processor generates the new binary operation by defining an operational result of (w, x) and (y, z) by the new binary operation as (zy+(1−z)r, xORz), where r is an operational result of w and y by the binary operation, and OR is an operator indicating the logical sum.
3 . The cumulative calculation device according to claim 1 , wherein the processor extracts u=(u 1 , . . . , u n ) as s i ′=(u i , d i ), and outputs the extracted u.
4 . A cumulative calculation method performed by a cumulative calculation device including a memory and a processor that, with respect to a column v=(v 1 , . . . v n ) of n values divided into groups, calculates cumulation for each of the groups through an associative binary operation, the method comprising:
forming c=(c 1 , . . . , c n ) as a column of values in which 1 corresponds to a head element of a group and 0 corresponds to elements other than the head element among elements v 1 , . . . , v n of v:
converting v into v′=(v 1 ′, . . . , v n ′) (where v i ′=(v i , c i ))
generating a new binary operation for calculating a new pair (p, q) for two pairs (w, x) and (y, z) (where x, z ∈ {0, 1}) using the binary operation;
calculating a cumulative s i ′ (where s i ′ is cumulation from v 1 ′ to v i ′ from the new binary operation) by the new binary operation for i=1, . . . , n; and
extracting a column u=(u 1 , . . . , u n ) of values indicating the cumulation for said each of the groups from each s i ′ (where i=1, . . . , n) and outputting the extracted u,
wherein the new binary operation sets an operation result of w and y by the binary operation to p when z=0, sets y to p when z=1, and sets a logical sum of x and z to q.
5 . A non-transitory computer-readable recording medium having computer-readable instructions stored thereon, which, when executed, cause a computer to execute a method that, with respect to a column v=(v 1 , . . . , v n ) of n values divided into groups, calculates cumulation for each of the groups through an associative binary operation,
the method comprising:
forming c=(c 1 , . . . , c n ) as a column of values in which 1 corresponds to a head element of a group and 0 corresponds to elements other than the head element among elements v 1 , . . . , v n of v:
converting v into v′=(v 1 ′, . . . , v n ) (where v 1 ′=(v 1 , c i )):
generating a new binary operation for calculating a new pair (p, q) for two pairs (w, x) and (y, z) (where x, z ∈ {0, 1}) using the binary operation:
calculating a cumulative s i ′ (where s i ′ is cumulation from v 1 ′ to v i ′ from the new binary operation) by the new binary operation for i=1, . . . , n; and
extracting a column u=(u 1 , . . . , u n ) of values indicating the cumulation for said each of the groups from each s i ′ (where i=1, . . . , n) and outputting the extracted u,
wherein the new binary operation sets an operation result of w and y by the binary operation to p when z=0, sets y to p when z=1, and sets a logical sum of x and z to q.