Programming puzzle: highest proportion of 1s in a substring

[barbos]

You are moving goalposts. I'm not saying without delay, just in constant time. In one frame all adders produce shifted bits to all output registers, and all additions happen in a fixed number of operations. That is constant time. It is potentially TRIVIALLY so, except for the fact that all results are rendered here in two-step, first for shifts and then for additions.

I am not moving anything, Constant delay is the same thing as zero delay or rather minimum delay.
Addition involves "carry out" bits and that creates delays which can be reduced only by increasing complexity of the logic which in the end increase power use. Programmers who don't know the basics of ALU sadden me.

We aren't talking time delay. We are talking about a math problem.

Namely one that says for any multiplication of two integers, there is an operation in constant time that can solve it, and all for any other combination with a smaller result. (Technically, it can solve for any combination with an equal sum total magnitude, or 1111*1 represents the same bit depth as 11*11).

You can not add/multiply arbitrary long numbers in constant time, period.
You can't even add numbers in the same time as bitwise operation.
Addition is fundamentally more complicated than bitwise operations.

 

[Bomb#20]

Constant time regardless of the size of the number? 16 bit, 32 bit, 64 bit, 10^10 bit long, the same time?
I find that hard to believe.
Multiplication is naturally O(N^2) problem. Though, there are algorithms which are better than O(N^2) but they work only on extremely long numbers, 10^10 digits kind of numbers

Actually, the Karatsuba method is O(N^1.58) and is highly practical for "normal"-sized numbers, i.e., the sizes that come up in internet packet encryption, typically 1024 bits. I designed hardware implementations using it at a chip company I used to work for. The methods that only speed you up on 10^10 digits kind of numbers are ones like Fürer's algorithm that are even better than Karatsuba.

 

[barbos]

Constant time regardless of the size of the number? 16 bit, 32 bit, 64 bit, 10^10 bit long, the same time?
I find that hard to believe.
Multiplication is naturally O(N^2) problem. Though, there are algorithms which are better than O(N^2) but they work only on extremely long numbers, 10^10 digits kind of numbers

Actually, the Karatsuba method is O(N^1.58) and is highly practical for "normal"-sized numbers, i.e., the sizes that come up in internet packet encryption, typically 1024 bits. I designed hardware implementations using it at a chip company I used to work for. The methods that only speed you up on 10^10 digits kind of numbers are ones like Fürer's algorithm that are even better than Karatsuba.

Indeed, I now remember reading about it but for some reason I only remembered the Fürer's. I think I assumed they are both for very very long numbers and remembered the best one.
I wonder if it used in python and CPUs

In March 2019, Harvey and van der Hoeven published a long-sought after {\displaystyle O(n\log n)}O(n\log n) integer multiplication algorithm, which is conjectured to be asymptotically optimal.[11][12] Because Schönhage and Strassen predicted that n log is the ‘best possible’ result Harvey said: “...our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously.”

They are still improving it.

 

[J842P]

I wonder if it used in python and CPUs

In CPython, it is used after a certain cutoff:

https://github.com/python/cpython/b...a5f94fe0160ddb1536/Objects/longobject.c#L3257

 

[barbos]

I wonder if it used in python and CPUs

In CPython, it is used after a certain cutoff:

https://github.com/python/cpython/b...a5f94fe0160ddb1536/Objects/longobject.c#L3257

Makes sense.

 

[lpetrich]

In this problem, do the 0's and 1's in the substring have to be contiguous in the original string?

If the original string has length n and the substring length k, then if the substring's bits are contiguous, then (n - k + 1) substrings, otherwise n!/(k!*(n-k)!), ignoring substring orders. That's safe to do if all one wants is the substring's count of 1's. In fact, the problem becomes almost absurdly easy in the noncontinguous case. Count the number of 1's in the original string: c. Then the maximum number of 1's in a length-k substring is min(c,k).

In the contiguous case, one can do the problem with two nested loops. Is there supposed to be some faster way?

Pseudocode for list of 0's and 1's: BitList

// Not the correct value of the count, but it will be corrected in the first iteration of the loop
BestIndex = 0
BestCount = 0

for i = 0 to (n-k)
. // Find sum of bits for this substring
. // This counts how many 1's in it
. Count = 0
. for j = 0 to k-1
. . Count += BitList[i+j]
. end for
. // Does this count improve on the previous best value?
. // It uses the first max-value substring that it finds
. if Count > BestCount then
. . BestIndex = i
. . BestCount = Count
. end if
end for

 

[Jayjay]

In this problem, do the 0's and 1's in the substring have to be contiguous in the original string?

As you pointed out yourself, the "non-contiguous" case is just about counting 1s until you reach k and is trivial, so obviously the problem is about a contiguous substring.

In the contiguous case, one can do the problem with two nested loops. Is there supposed to be some faster way?

Pseudocode for list of 0's and 1's: BitList

// Not the correct value of the count, but it will be corrected in the first iteration of the loop
BestIndex = 0
BestCount = 0

for i = 0 to (n-k)
. // Find sum of bits for this substring
. // This counts how many 1's in it
. Count = 0
. for j = 0 to k-1
. . Count += BitList[i+j]
. end for
. // Does this count improve on the previous best value?
. // It uses the first max-value substring that it finds
. if Count > BestCount then
. . BestIndex = i
. . BestCount = Count
. end if
end for

Well, read the beginning of the thread for answers. Spoilers:

Show

The first obvious optimization that barbos pointed out was that the maximum length of the substring is 2k-1. And the second optimization is to check if any of the best substrings for k can be expanded by adjacents 1s either before or after it, which will give you best answers for k+1 without having to check every substring.

Also, I think you still misunderstood. The problem was not to find the highest count of 1s, but highest proportion of 1s in a substring. And the substring length may be greater than k.