Interpolating/estimating f on subset of integers
$begingroup$
Here is the question I have been struggling to solve lately. Imagine we have two integers $x, y in mathbb Z, x le y$ and $Y = { a | a in mathbb Z and x le a le y }$; $Xsubset Y$. In the context of this specific question think of $|Y| approx 10000$.
We want to find function $f: Y rightarrow {0,1}$ such that, $f(x) = 1 iff x in X$.
Now the worst I can do is basically do the interpolation which will grow quite fast. I think we could do better using the fact that this function has to be only defined on integers, not on real line. I want to find $f$ that is cheap to compute (preferably bitwise operations).
Obviously it very much depends on the nature of the $Y$. For example, if the set contains only odd/even integers then finding $f$ becomes trivial. How would I generally approach this problem? I thought about decomposing the set into arithmetic progressions and then checking for each of them, but that does not seem to be very promising approach.
discrete-mathematics boolean-algebra interpolation
asked Jan 10 at 1:12
JukesOnYouJukesOnYou
57638
$endgroup$
|
show 1 more comment
$begingroup$
Here is the question I have been struggling to solve lately. Imagine we have two integers $x, y in mathbb Z, x le y$ and $Y = { a | a in mathbb Z and x le a le y }$; $Xsubset Y$. In the context of this specific question think of $|Y| approx 10000$.
We want to find function $f: Y rightarrow {0,1}$ such that, $f(x) = 1 iff x in X$.
Now the worst I can do is basically do the interpolation which will grow quite fast. I think we could do better using the fact that this function has to be only defined on integers, not on real line. I want to find $f$ that is cheap to compute (preferably bitwise operations).
Obviously it very much depends on the nature of the $Y$. For example, if the set contains only odd/even integers then finding $f$ becomes trivial. How would I generally approach this problem? I thought about decomposing the set into arithmetic progressions and then checking for each of them, but that does not seem to be very promising approach.
discrete-mathematics boolean-algebra interpolation
asked Jan 10 at 1:12
JukesOnYouJukesOnYou
57638
$endgroup$
$begingroup$
Let the binary number $Q$ have a 1 for its $r$th bit if $r$ is in $X$, else a zero. Then $f(z)$ is the $z$th bit of $Q$.
$endgroup$
– Gerry Myerson
Jan 10 at 1:25
$begingroup$
Storing $|Y|$ bits is not really feasible
$endgroup$
– JukesOnYou
Jan 10 at 1:30
$begingroup$
That depends on how big $Y$ is. So maybe you have some considerations in mind that you have not made explicit in your question, and maybe you should work out what they are and edit them into the question.
$endgroup$
– Gerry Myerson
Jan 10 at 1:35
$begingroup$
Good point, I edited question!
$endgroup$
– JukesOnYou
Jan 10 at 11:14
$begingroup$
10,000 bits doesn't seem like a lot to me. I'm surprised storing that many bits isn't feasible.
$endgroup$
– Gerry Myerson
Jan 10 at 15:01
|
show 1 more comment
$begingroup$
Here is the question I have been struggling to solve lately. Imagine we have two integers $x, y in mathbb Z, x le y$ and $Y = { a | a in mathbb Z and x le a le y }$; $Xsubset Y$. In the context of this specific question think of $|Y| approx 10000$.
We want to find function $f: Y rightarrow {0,1}$ such that, $f(x) = 1 iff x in X$.
Now the worst I can do is basically do the interpolation which will grow quite fast. I think we could do better using the fact that this function has to be only defined on integers, not on real line. I want to find $f$ that is cheap to compute (preferably bitwise operations).
Obviously it very much depends on the nature of the $Y$. For example, if the set contains only odd/even integers then finding $f$ becomes trivial. How would I generally approach this problem? I thought about decomposing the set into arithmetic progressions and then checking for each of them, but that does not seem to be very promising approach.
discrete-mathematics boolean-algebra interpolation
asked Jan 10 at 1:12
JukesOnYouJukesOnYou
57638
$endgroup$
Here is the question I have been struggling to solve lately. Imagine we have two integers $x, y in mathbb Z, x le y$ and $Y = { a | a in mathbb Z and x le a le y }$; $Xsubset Y$. In the context of this specific question think of $|Y| approx 10000$.
We want to find function $f: Y rightarrow {0,1}$ such that, $f(x) = 1 iff x in X$.
Now the worst I can do is basically do the interpolation which will grow quite fast. I think we could do better using the fact that this function has to be only defined on integers, not on real line. I want to find $f$ that is cheap to compute (preferably bitwise operations).
Obviously it very much depends on the nature of the $Y$. For example, if the set contains only odd/even integers then finding $f$ becomes trivial. How would I generally approach this problem? I thought about decomposing the set into arithmetic progressions and then checking for each of them, but that does not seem to be very promising approach.
discrete-mathematics boolean-algebra interpolation
discrete-mathematics boolean-algebra interpolation
asked Jan 10 at 1:12
JukesOnYouJukesOnYou
57638
asked Jan 10 at 1:12
JukesOnYouJukesOnYou
57638
edited Jan 10 at 11:13
JukesOnYou
asked Jan 10 at 1:12
JukesOnYouJukesOnYou
57638
asked Jan 10 at 1:12
JukesOnYouJukesOnYou
57638
asked Jan 10 at 1:12
JukesOnYouJukesOnYou
57638
57638
$begingroup$
Let the binary number $Q$ have a 1 for its $r$th bit if $r$ is in $X$, else a zero. Then $f(z)$ is the $z$th bit of $Q$.
$endgroup$
– Gerry Myerson
Jan 10 at 1:25
$begingroup$
Storing $|Y|$ bits is not really feasible
$endgroup$
– JukesOnYou
Jan 10 at 1:30
$begingroup$
That depends on how big $Y$ is. So maybe you have some considerations in mind that you have not made explicit in your question, and maybe you should work out what they are and edit them into the question.
$endgroup$
– Gerry Myerson
Jan 10 at 1:35
$begingroup$
Good point, I edited question!
$endgroup$
– JukesOnYou
Jan 10 at 11:14
$begingroup$
10,000 bits doesn't seem like a lot to me. I'm surprised storing that many bits isn't feasible.
$endgroup$
– Gerry Myerson
Jan 10 at 15:01
|
show 1 more comment
$begingroup$
Let the binary number $Q$ have a 1 for its $r$th bit if $r$ is in $X$, else a zero. Then $f(z)$ is the $z$th bit of $Q$.
$endgroup$
– Gerry Myerson
Jan 10 at 1:25
$begingroup$
Storing $|Y|$ bits is not really feasible
$endgroup$
– JukesOnYou
Jan 10 at 1:30
$begingroup$
That depends on how big $Y$ is. So maybe you have some considerations in mind that you have not made explicit in your question, and maybe you should work out what they are and edit them into the question.
$endgroup$
– Gerry Myerson
Jan 10 at 1:35
$begingroup$
Good point, I edited question!
$endgroup$
– JukesOnYou
Jan 10 at 11:14
$begingroup$
10,000 bits doesn't seem like a lot to me. I'm surprised storing that many bits isn't feasible.
$endgroup$
– Gerry Myerson
Jan 10 at 15:01
$begingroup$
Let the binary number $Q$ have a 1 for its $r$th bit if $r$ is in $X$, else a zero. Then $f(z)$ is the $z$th bit of $Q$.
$endgroup$
– Gerry Myerson
Jan 10 at 1:25
$begingroup$
Let the binary number $Q$ have a 1 for its $r$th bit if $r$ is in $X$, else a zero. Then $f(z)$ is the $z$th bit of $Q$.
$endgroup$
– Gerry Myerson
Jan 10 at 1:25
$begingroup$
Storing $|Y|$ bits is not really feasible
$endgroup$
– JukesOnYou
Jan 10 at 1:30
$begingroup$
Storing $|Y|$ bits is not really feasible
$endgroup$
– JukesOnYou
Jan 10 at 1:30
$begingroup$
That depends on how big $Y$ is. So maybe you have some considerations in mind that you have not made explicit in your question, and maybe you should work out what they are and edit them into the question.
$endgroup$
– Gerry Myerson
Jan 10 at 1:35
$begingroup$
That depends on how big $Y$ is. So maybe you have some considerations in mind that you have not made explicit in your question, and maybe you should work out what they are and edit them into the question.
$endgroup$
– Gerry Myerson
Jan 10 at 1:35
$begingroup$
Good point, I edited question!
$endgroup$
– JukesOnYou
Jan 10 at 11:14
$begingroup$
Good point, I edited question!
$endgroup$
– JukesOnYou
Jan 10 at 11:14
$begingroup$
10,000 bits doesn't seem like a lot to me. I'm surprised storing that many bits isn't feasible.
$endgroup$
– Gerry Myerson
Jan 10 at 15:01
$begingroup$
10,000 bits doesn't seem like a lot to me. I'm surprised storing that many bits isn't feasible.
$endgroup$
– Gerry Myerson
Jan 10 at 15:01
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
Basically you are asking for a search routine.
They are not very cheap.
For repeated searches, pay the overhead of sorting X.
Yes, if X has a nonrandom structure such as even numbers only,
that structure can be taken advantage of for a quick search.
Being a factor of seven wouldn't be as quick.
Will your data be structure so a program could be written
that would be cheaper than a general search routine?
answered Jan 10 at 3:05
William ElliotWilliam Elliot
8,9662820
$endgroup$
$begingroup$
In my case the set $X$ is fixed, but with no obvious pattern. Yes one idea that works fine is having basically precomputed truth table for each $x in Y$, but memory is quite expensive resource (fetching memory is much slower than calculating bitwise operations), so I wanted to encode that information somehow in function, as evaluation of this function is much cheaper.
$endgroup$
– JukesOnYou
Jan 10 at 11:09
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3068127%2finterpolating-estimating-f-on-subset-of-integers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Basically you are asking for a search routine.
They are not very cheap.
For repeated searches, pay the overhead of sorting X.
Yes, if X has a nonrandom structure such as even numbers only,
that structure can be taken advantage of for a quick search.
Being a factor of seven wouldn't be as quick.
Will your data be structure so a program could be written
that would be cheaper than a general search routine?
answered Jan 10 at 3:05
William ElliotWilliam Elliot
8,9662820
$endgroup$
$begingroup$
In my case the set $X$ is fixed, but with no obvious pattern. Yes one idea that works fine is having basically precomputed truth table for each $x in Y$, but memory is quite expensive resource (fetching memory is much slower than calculating bitwise operations), so I wanted to encode that information somehow in function, as evaluation of this function is much cheaper.
$endgroup$
– JukesOnYou
Jan 10 at 11:09
add a comment |
$begingroup$
Basically you are asking for a search routine.
They are not very cheap.
For repeated searches, pay the overhead of sorting X.
Yes, if X has a nonrandom structure such as even numbers only,
that structure can be taken advantage of for a quick search.
Being a factor of seven wouldn't be as quick.
Will your data be structure so a program could be written
that would be cheaper than a general search routine?
answered Jan 10 at 3:05
William ElliotWilliam Elliot
8,9662820
$endgroup$
$begingroup$
In my case the set $X$ is fixed, but with no obvious pattern. Yes one idea that works fine is having basically precomputed truth table for each $x in Y$, but memory is quite expensive resource (fetching memory is much slower than calculating bitwise operations), so I wanted to encode that information somehow in function, as evaluation of this function is much cheaper.
$endgroup$
– JukesOnYou
Jan 10 at 11:09
add a comment |
$begingroup$
Basically you are asking for a search routine.
They are not very cheap.
For repeated searches, pay the overhead of sorting X.
Yes, if X has a nonrandom structure such as even numbers only,
that structure can be taken advantage of for a quick search.
Being a factor of seven wouldn't be as quick.
Will your data be structure so a program could be written
that would be cheaper than a general search routine?
answered Jan 10 at 3:05
William ElliotWilliam Elliot
8,9662820
$endgroup$
Basically you are asking for a search routine.
They are not very cheap.
For repeated searches, pay the overhead of sorting X.
Yes, if X has a nonrandom structure such as even numbers only,
that structure can be taken advantage of for a quick search.
Being a factor of seven wouldn't be as quick.
Will your data be structure so a program could be written
that would be cheaper than a general search routine?
answered Jan 10 at 3:05
William ElliotWilliam Elliot
8,9662820
answered Jan 10 at 3:05
William ElliotWilliam Elliot
8,9662820
answered Jan 10 at 3:05
William ElliotWilliam Elliot
8,9662820
answered Jan 10 at 3:05
William ElliotWilliam Elliot
8,9662820
8,9662820
$begingroup$
In my case the set $X$ is fixed, but with no obvious pattern. Yes one idea that works fine is having basically precomputed truth table for each $x in Y$, but memory is quite expensive resource (fetching memory is much slower than calculating bitwise operations), so I wanted to encode that information somehow in function, as evaluation of this function is much cheaper.
$endgroup$
– JukesOnYou
Jan 10 at 11:09
add a comment |
$begingroup$
In my case the set $X$ is fixed, but with no obvious pattern. Yes one idea that works fine is having basically precomputed truth table for each $x in Y$, but memory is quite expensive resource (fetching memory is much slower than calculating bitwise operations), so I wanted to encode that information somehow in function, as evaluation of this function is much cheaper.
$endgroup$
– JukesOnYou
Jan 10 at 11:09
$begingroup$
In my case the set $X$ is fixed, but with no obvious pattern. Yes one idea that works fine is having basically precomputed truth table for each $x in Y$, but memory is quite expensive resource (fetching memory is much slower than calculating bitwise operations), so I wanted to encode that information somehow in function, as evaluation of this function is much cheaper.
$endgroup$
– JukesOnYou
Jan 10 at 11:09
$begingroup$
In my case the set $X$ is fixed, but with no obvious pattern. Yes one idea that works fine is having basically precomputed truth table for each $x in Y$, but memory is quite expensive resource (fetching memory is much slower than calculating bitwise operations), so I wanted to encode that information somehow in function, as evaluation of this function is much cheaper.
$endgroup$
– JukesOnYou
Jan 10 at 11:09
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3068127%2finterpolating-estimating-f-on-subset-of-integers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Let the binary number $Q$ have a 1 for its $r$th bit if $r$ is in $X$, else a zero. Then $f(z)$ is the $z$th bit of $Q$.
$endgroup$
– Gerry Myerson
Jan 10 at 1:25
$begingroup$
Storing $|Y|$ bits is not really feasible
$endgroup$
– JukesOnYou
Jan 10 at 1:30
$begingroup$
That depends on how big $Y$ is. So maybe you have some considerations in mind that you have not made explicit in your question, and maybe you should work out what they are and edit them into the question.
$endgroup$
– Gerry Myerson
Jan 10 at 1:35
$begingroup$
Good point, I edited question!
$endgroup$
– JukesOnYou
Jan 10 at 11:14
$begingroup$
10,000 bits doesn't seem like a lot to me. I'm surprised storing that many bits isn't feasible.
$endgroup$
– Gerry Myerson
Jan 10 at 15:01