0

Background

I am working on a project involving FPGA's (a configurable logic circuit) and modulus of numbers to determine if $X$ is divisible by $Y$. When I take the modulus of a number a full division circuit is used which uses to many of the FPGA's resources.

The Question

Is it possible to know if $X$ is divisible by $Y$ without completing the full division process? I know that there are specific rules for numbers like $2$ and $3$, but is there a general one?

Is it possible to know if it is divisible part way through the division process without completing it?

Update

$Y$'s range is from $2$ to sqrt($X$).

I can make $Y$ be the set of numbers $A$ * $K$ + $C$ where $K$ and $C$ are constant.

This is my first post on this page so let me know if I made a mistake or if it should be in a Computer Science or Electrical Engineering page instead because of the content of the actual math and not the implementation

Also please edit tags as I am not sure how to tag questions here

Eric Johnson
  • 115
  • 1
  • 8
  • Do you have a limited list of $Y$s of interest, or can $Y$ be anything? For any specific $Y$ you can find a rule. – Ross Millikan Mar 09 '16 at 01:19
  • $Y$<$X$, but it could be taken to $Y$<sqrt($X$) to make it simpler. – Eric Johnson Mar 09 '16 at 01:25
  • 1
    There are lots of possibilities (maybe something along the lines of Silver and Terzian's binary GCD algorithm which I'll think you'll find in Knuth). But to get a good algorithm for your hardware and software is not really an MSE topi, so you'll do better to ask you question on a programming forum like http://stackoverflow.com. – Rob Arthan Mar 09 '16 at 02:12
  • To follow up in response to @RobArthan 's comments on my answer, I assumed the question was about the mathematics of such rules, as this is M.SE. If you have algorithmic questions, that's better suited for CS.SE – Stella Biderman Mar 09 '16 at 02:41

1 Answers1

1

There are ad hoc solutions for most values of $Y$, but no general answers. If you have particular numbers or forms of numbers in mind we can be more detailed.

Stella Biderman
  • 31,155
  • I have updated the question with a more particular number set for $Y$. – Eric Johnson Mar 09 '16 at 01:45
  • @EricJohnson That's not a very helpful expression unfortunately. Are you looking for answers for a large swathe of numbers? – Stella Biderman Mar 09 '16 at 01:47
  • Yes. I am doing between 2 and 2^64 for $X$ so between 2 and 2^32 for $Y$. – Eric Johnson Mar 09 '16 at 01:50
  • 1
    @EricJohnson If $Y$ takes on all values from $2$ to $2^32$ then there is no hope for such a thing. It's, at a minimum, a few lines per $Y$, which would be ludicrously long to possibly write down – Stella Biderman Mar 09 '16 at 01:56
  • @StellaBiderman: do you know the performance characteristics of the FPGA hardware that Eric is using? How can you pontificate on the impossibility of his finding a solution to his problem that is more efficient than simplistic use of a division instruction without knowing that? – Rob Arthan Mar 09 '16 at 02:21
  • No, I mean that since there is no general schema, we don't have the ability to list divisibility criteria like the OP asks for. – Stella Biderman Mar 09 '16 at 02:23
  • The OP is not asking for a "general schema" but for help with a specific software/hardware design task. Your "there is no hope for such a thing" is focussing on a detail of the OP's question that is of least importance to him. – Rob Arthan Mar 09 '16 at 02:33