Questions tagged [integers]

Questions about properties of, working with and algorithms on integers.

Filter by
Sorted by
Tagged with
0
votes
1answer
23 views

For signed integers, why don't representative the smallest number as all zeros in binary, and the largest as all ones?

I'm reading up on bitwise operators, complements, and two's complements, and I'm wondering why the lower limit of a range (aka lowest negative number) isn't all zeroes in binary, and the upper limit ...
1
vote
1answer
28 views

What is the equivalent of the integers symbol Z for n bit only integers?

We refer to the set of all integers as $\mathbb{Z}$. Now suppose we have a set of integers that can be held within a computer variable of $n$ bits width. Clearly they can only be of $2^{n}$ range, ...
3
votes
1answer
48 views

Reversible Merge of Integer Hash Values

Context: I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's ...
1
vote
2answers
103 views

Efficient data structure for storing integers in a range?

Say I'm constantly given integers from the range $[1,2^{32}]$ in a random order and have to store these so that when a duplicate arrives I can deal with it. By the end of this algorithm all $2^{32}$ ...
1
vote
0answers
11 views

Structure of numbers in descriptive complexity

Descriptive complexity is a useful way to free yourself from computational considerations when studying complexity. One of those considerations is the encoding of the structures you are working on. ...
1
vote
0answers
19 views

Partitioning the columns of a matrix

I thought about this problem for a while now and am not able to find a solution for it, be it a direct algorithm or a reduction to a known problem, so I'm asking here: Suppose you have a matrix $A\in\...
1
vote
0answers
94 views

How does prefix summing the count histogram in counting sort result in an array of output indices?

My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is: ...
2
votes
0answers
22 views

Is finding a sum of two squares representation for a number computationally assymptotically equivalent to integer factorization?

I have been wondering this question because given a number $n$ with prime factors of the form $4k+3$ when we square $n$ and find a sum of two squares which should reveal these types of factors (as ...
0
votes
1answer
55 views

Why are floats converted from different integers sometimes equal?

I'm trying to understand the following algorithm: ...
1
vote
1answer
84 views

Algorithm for implementing the modulus “%” operator?

How can an efficient modulus operator be implemented? Here's a naive way of defining A % B: given $(a,b) \in \mathbb{Z}$ (represented as ...
0
votes
0answers
36 views

Using half float to represent scaled short (int16), do I lose precision comparing to using double?

A device is generating 14-bit integer which is stored as int16 (short), a scaling process will then scale the data to value of order 10E-3. Does it then matter if I store these number with half float ...
3
votes
1answer
67 views

Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?

Context, I have a geometric algorithm that is sensitive to collinear points and receives as input a list of points in 2D generated randomly. Suppose that I have a Boolean function nonCollinear(x,y,z) ...
0
votes
1answer
19 views

Merge Sort meaning of a bit part of code

I am studying this part for a merge sort implementation: ...
2
votes
1answer
311 views

How to read off the set represented by a van-Emde-Boas tree?

I'm reviewing my background in Algorithms and DS design. Specifically I never went through the van Emde Boas Tree. Though I can undestand the proto-vEB with related picture. I'm struggling to ...
3
votes
0answers
42 views

Sets whose decimal expansions form a regular language

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). For a set $S$ of natural numbers, let its set of expansions (in base 10) be $\bar S = \{\bar n \...
0
votes
0answers
44 views

Improving an integer factoring algorithm

I've written an algorithm for integer factorization (specifically RSA-like coprimes - products of two large primes, roughly of the same number of decimal digits) which is not based on QS, GNFS or any ...
3
votes
0answers
76 views

Given two arrays of length n and n - 1, order the first array such that no partial sum is in the second array

Two arrays of natural numbers are given of length $n$ and $n - 1$: e.g. $A: [a_0, a_1,..., a_{n-1}, a_n]$ $B: [b_0, b_1, ..., b_{n-2}, b_{n-1}]$ All elements of $A$ are unique (can be in $B$), all ...
1
vote
2answers
61 views

Find all pairs (i, j), such that i + (i+1) + (i+2) + … + j = n

We have give positive integer $n$, and we want to find all the pairs $(i, j), i\leq j$ such that: $$i + (i+1) +(i+2)+(i+3)+ \dots + j = n$$ Clearly we can try all possible pairs in $O(N^2)$, but that ...
0
votes
1answer
71 views

Mistake in the Algorithm Design Manual?

Look at this excerpt from the Algorithm Design Manual by Skiena, 2nd Edition The sum of the first $n$ even integers? Surely, the two sums given do not include only even numbers, right? Is this a ...
3
votes
1answer
151 views

Linear time multiplication on RAM machine?

This page says following: Integer Multiplication has an O-optimal linear-time algorithm on a RAM or SMM Is this page fooling me or how can we multiply 2 numbers in linear time (bitwise complexity) ...
1
vote
1answer
54 views

Compress 32 bit integer into a normalized float

and sorry if this is a duplicate of some sort, my poor technical vocabulary doesn't get me very far with google. I am trying to implement some well-known PRNG algorithms. For the time, the algorithm ...
3
votes
2answers
84 views

How to find the closest N to the power of X to the given number?

Let's say we have number 4920 and we want to find the closest $n^x$ to 4920 2 ^ 12 = 4096 but it's not the closest possible $n^x$, for example 17 ^ 3 = 4913 is closer to 4920 The question is, how do ...
2
votes
1answer
64 views

Swap elements using integer addition and multiplication gates

I need to swap two integers using only integer addition and multiplication gates. I can't subtract them. I'm dealing with a sorting network, so I need to compare and swap. The compare and swap ...
1
vote
1answer
27 views

Gray-like code with maximum value <= maximum value of original symbol

I want to iterate through the numbers $0,1,2,\dots,n-1$ in some order, where each number in the sequence differs by only one bit from the previous bit. I'm going to be using each number as an index ...
3
votes
0answers
65 views

Low-level division operator implementation

A few weeks ago, I asked this question on the implementation of the shift operator for an architecture that implements boxing. Reviewing my implementation I found out that the division operator wasn't ...
3
votes
1answer
58 views

Low-level shift operator implementation

I want a shift operator for an architecture that implements boxing. Basically, the high-level constructs represent integers as 31 bits followed by 1 bit set to one as a tag (so to represent binary int ...
1
vote
1answer
303 views

4-partition elements summation NP completeness

How can we prove that the following problem $A$ is NP complete? Given a set of integers $S={a_1, ..., a_n}$ and a number $D$, is it possible to find disjoint sets $S_1, S_2, S_3, S_4$ such that $S_1 \...
0
votes
1answer
57 views

How to determine the carry vector of an integer addition

An integer addition can be represented as following: $A + B = A \oplus B \oplus carry_{vector}$ My question is how to determine the carry vector from $A$ and $B$ (not from the result)?
2
votes
1answer
137 views

How to uniquely encode a vector of non-increasing positive integers

Given a vector of positive integers $A=[a_1, \cdots, a_n]$, where $\sum_{1 \leq i \leq n}a_i = n(n-1)$ and $a_i \geq a_j$ iff $i \geq j$, I am interested in encoding the vector, maintaining the ...
5
votes
0answers
82 views

What are applications to sort plain integer arrays?

A lot of research and engineering effort is put into finding fast methods to sort an array of integers; e.g., Java's runtime library has highly-tuned methods to sort arrays of each primitive type (see ...
2
votes
1answer
1k views

Complexity of Integer Division

My favourite algorithm textbook: The Algorithm Design Manual S. Skiena.pdf had this interesting problem: 1-28. [5] Write a function to perform integer division without using either the / or * ...
1
vote
1answer
254 views

There are n numbers. Find the maximal set of pairwise NON coprime numbers

I have to take input in an array(no. of elements in array <=10^5). For ex:- Let the array be {2,3,4,16,9,45,81,27} Now I need to find the order of the maximal set such that any pair of elements in ...
1
vote
1answer
144 views

Complexity class of integer factorization

Is integer factorization confirmed to be an NP-complete problem? If not, then if one could transform IF into an equivalent problem which is already proved to be NP-complete, would it mean that IF is ...
2
votes
2answers
364 views

Find the duplicates in a list of floating point numbers

I receive a list of real numbers ( float ) between $0$ and $1$. The list has length $N+1$ and I need to find two numbers on the list which are $\le \frac{1}{N}$ ...
1
vote
2answers
107 views

Problems that become far easier when restricted to only integer values

I know that there are some problems that are very hard to solve in general, but become much easier and asymptotically faster if restricted to only integer values. One such example would be sorting ...
2
votes
2answers
174 views

Efficient algorithm for getting from 1 to n with 3 specific operations

The question: Given those 3 valid operations over numbers and an integer $n$: add $1$ to the number multiply the number by $2$ multiply the number by $3$ describe an efficient ...
2
votes
0answers
52 views

Are there any practical drop-in replacements for BSTs in the case where data are integers?

There are a number of specialized data structures that implement ordered dictionaries for integer keys: van Emde Boas trees, y-Fast tries, fusion trees, etc. Each of these data structures implement ...
1
vote
3answers
3k views

Sum of 3 integers with full adder

1)Is it possible for a full adder to add three e.g 4 bit numbers? I mean I know the full adder has 3 inputs and two outputs but the second bit of C comes from the previous block (as shown in the image ...
1
vote
1answer
627 views

Convert integer of mixed radix to standard positional numeral system and vice versa

I have multiple numbers (e.g. [1, 4, 2]) where each number can be one of a specified range of numbers (e.g. [0-1, 0-5, 0-3]). I ...
3
votes
0answers
20 views

Numerical Stability of Halley's Recurrence for Integer $n^{\mathrm{th}}$-Root

tl;dr? See last paragraph. If I use the initial value $2^{\left(\big\lfloor\lfloor\log_2 x \rfloor/n\big\rfloor + 1\right)}$ with Halley's recurrence in the compact form $ x_{k+1} = \frac{x_k\Big[A\...
4
votes
1answer
250 views

Optimal quantization of histogram

I have a histogram of occurrences, as a list of counts (non-negative integers). For the purposes of a compression algorithm (specifically arithmetic coding) I must quantize these occurrences into a ...
4
votes
1answer
22 views

Compactly representing integers when allowed a multiplicative error

Consider the problem of representing in memory numbers in the range $\{1,\ldots,n\}$. Obviously, exact representation of such number requires $\lceil\log_2(n)\rceil$ bits. In contrast, assume we are ...
3
votes
1answer
247 views

Where can I find an original reference for this integer square root algorithm

As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary. I'm sure this is not original; can anyone provide a reference? ...
1
vote
1answer
62 views

Sum to a certain value of a group of integers

Take a group filled with an arbitrary number of random integers. Is there any way of finding out whether it is possible for the sum of the integers can equal a certain number, with the condition that ...
3
votes
2answers
92 views

Can one increment an $n$ bit integer using fewer than $2 - 2^{1-n}$ bit inspections on average?

Given an $n$-bit integer, I am interested in performing an increment operation using as few bit reads as possible. The standard binary code (standard binary representation of numbers), requires $n$ ...
2
votes
4answers
510 views

Counting an integer's divisors without just enumerating them (or estimating if not possible)?

I'm trying to count the number of divisors an integer $n$ has. The simple way to do this is to just enumerate all integers from 1 to $\sqrt{n}$, and count how many integers evenly divide $n$. For ...
5
votes
1answer
141 views

Practical Implementation for Refinement Order on Integer Partitions

The refinement order on partitions of an integer $n$ can be defined as follows: $\lambda=(\lambda_1,\dots,\lambda_k)\leq\mu=(\mu_1,\dots,\mu_\ell)$ if there is a partition of the parts of $\lambda$ ...
21
votes
3answers
1k views

Algorithm to minimize surface area, given volume

Consider the following algorithmic task: Input: a positive integer $n$, along with its prime factorization Find: positive integers $x,y,z$ that minimize $xy+yz+xz$, subject to the restriction that $...
4
votes
2answers
425 views

Are nearly all natural numbers compressible?

A simple counting argument shows most strings can't be compressed to shorter strings. But, compression is usually defined using Kolmogorov complexity. A string is compressible if its Kolmogorov ...
23
votes
2answers
686 views

Efficient algorithm for 'unsumming' a set of sums

Given a multiset of natural numbers X, consider the set of all possible sums: $$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$ For example, $\textrm{sums}(\left\{1,5\right\...